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...
In this talk I will introduce constructions of finite graphs which
resemble some given infinite graph both in terms of their local
neighborhoods, and also their spectrum. These graphs can be thought
of as expander graphs with local constraints in a...
