A polynomial with nonnegative coefficients is strongly
log-concave if it and all of its derivatives are log-concave as
functions on the positive orthant. This rich class of polynomials
includes many interesting examples, such as homogeneous real...
Establishing inequalities among graph densities is a central
pursuit in extremal graph theory. One way to certify the
nonnegativity of a graph density expression is to write it as a sum
of squares or as a rational sum of squares. In this talk, we...
A polynomial with nonnegative coefficients is strongly
log-concave if it and all of its derivatives are log-concave as
functions on the positive orthant. This rich class of polynomials
includes many interesting examples, such as homogeneous real...
"Games against Nature" [Papadimitriou '85] are two-player games
of perfect information, in which one player's moves are made
randomly. Estimating the value of such games (i.e., winning
probability under optimal play by the strategic player) is
an...
Expander graphs in general, and Ramanujan graphs in particular,
have played an important role in computer science and pure
mathematics in the last four decades. In recent years the area of
high dimensional expanders (i.e. simplical complexes with...
A recent line of work has focused on the following question: Can
one prove strong unconditional lower bounds on the number of
samples needed for learning under memory constraints? We study an
extractor-based approach to proving such bounds for a...
I will discuss techniques, structural results, and open problems
from two of my recent papers, in the context of a broader area of
work on the motivating question: "how do we get the most from our
data?"
What combinatorial properties are likely to be satisfied by a
random subspace over a finite field? For example, is it likely that
not too many points lie in any Hamming ball of fixed radius? What
about any combinatorial rectangle of fixed side...
What can we say on a convex body from seeing its projections? In
the 80s, Lutwak introduced a collection of measurements that
capture this question. He called them the affine quermassintegrals.
They are affine invariant analogues of the classical...
