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...
Suppose we have a cancellative binary associative operation * on
a finite set X. We say that it is delta-associative if the
proportion of triples x, y, z such that x*(y*z) = (x*y)*z is at
least delta.
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
of...
We will talk about a recent result of Jeff Kahn, Bhargav
Narayanan, and myself stating that the threshold for the random
graph G(n,p) to contain the square of a Hamilton cycle is 1/sqrt n,
resolving a conjecture of Kühn and Osthus from 2012. For...
We prove that parallel repetition of the (3-player) GHZ game
reduces the value of the game polynomially fast to 0. That is, the
value of the GHZ game repeated in parallel t times is at most
$t^{-\Omega(1)}. Previously, only a bound of roughly 1 /...
How dense can a set of integers be while containing no
three-term arithmetic progressions? This is one of the classical
problems of additive combinatorics, and since the theorem of Roth
in 1953 that such a set must have zero density, there has
been...
