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...
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...