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
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...
Indistinguishability obfuscation, introduced by [Barak et. al.
Crypto’2001], aims to compile programs into unintelligible
ones while preserving functionality. It is a fascinating and
powerful object that has been shown to enable a host of new...
We prove new lower bounds on the well known Gap-Hamming problem
in communication complexity. Our main technical result is an
anti-concentration bound for the inner product of two independent
random vectors. We show that if A, B are arbitrary subsets...
Sometimes, it is possible to represent a complicated polytope as
a projection of a much simpler polytope. To quantify this
phenomenon, the extension complexity of a polytope P is defined to
be the minimum number of facets in a (possibly higher...
We introduce two new notions for polynomials associated with
discrete set-valued probability distributions. These notions
generalize well-studied properties like real-stability and
log-concavity, but unlike them robustly degrade under a number