Given an arbitrary graph, we show that if we are allowed to
modify (say) 1% of the edges then it is possible to obtain a much
smaller regular partition than in Szemeredi's original proof of the
regularity lemma. Moreover, we show that it is...
In this talk, I will give an overview on how PCPs, combined with
cryptographic tools, are used to generate succinct and efficiently
verifiable proofs for the correctness of computations. I will focus
on constructing (computationally sound)...
What is the largest number of projections onto k coordinates
guaranteed in every family of m binary vectors of length n? This
fundamental question is intimately connected to important topics
and results in combinatorics and computer science (Turan...
Tensor networks describe high-dimensional tensors as the
contraction of a network (or graph) of low-dimensional tensors.
Many interesting tensor can be succinctly represented in this
fashion -- from many-body ground states in quantum physics to
the...
Chernoff-type bounds study concentration of sums of independent
random variables and are extremely useful in various settings. In
many settings, the random variables may not be completely
independent but only have limited independence. One such...
For any unsatisfiable CNF formula F that is hard to refute in the
Resolution proof system, we show that a gadget-composed version of
F is hard to refute in any proof system whose lines are computed by
efficient communication protocols---or...
We present the first protocol allowing a classical computer to
interactively verify the result of an efficient quantum
computation. We achieve this by constructing a measurement
protocol, which allows a classical string to serve as a commitment
to a...
I will survey new lower-bound methods in communication complexity
that "lift" lower bounds from decision tree complexity. These
methods have recently enabled progress on core questions in
communication complexity (log-rank conjecture, classical-...
The Erdos-Rado sunflower conjecture is one of the tantalizing open
problems in combinatorics. In my talk, I will describe several
attempts on how to get improved bounds for it. These will lead to
surprising connections with several other...
