Non-constructive existence proofs, which establish the existence
of objects without furnishing an efficient algorithm to produce
examples, abound in mathematics. How hard is it, computationally,
to find objects whose existence is guaranteed non...
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...
