We give an algorithmic proof of Forster's Theorem, a fundamental
result in communication complexity. Our proof is based on a
geometric notion we call radial isotropic position which is related
to the well-known isotropic position of a set of vectors...
The question whether or not parallel repetition reduces the
soundness error is a fundamental question in the theory of
protocols. While parallel repetition reduces (at an exponential
rate) the error in interactive proofs and (at a weak
exponential...
Green and Tao used the existence of a dense subset
indistinguishable from the primes under certain tests from a
certain class to prove the existence of arbitrarily long prime
arithmetic progressions. Reingold, Trevisan, Tulsiani and Vadhan,
and...
I will discuss the Green-Tao proof for existence of arbitrarily
long arithmetic progressions in the primes. The focus will
primarily be on the parts of the proof which are related to notions
in complexity theory. In particular, I will try to...
Research in the area of privacy of data analysis has been
flourishing recently, with a rigorous notion such as differential
privacy regarding the desired level of privacy and sanitizing
algorithms matching the definition for many problems. Most
of...
I will first give an overview of several constructions of graph
sparsifiers and their properties. I will then present a method of
sparsifying a subgraph W of a graph G with optimal number of edges
and talk about the implications of subgraph...
I will survey some constructions of expander graphs using
variants of Kazhdan property T . First, I describe an approach to
property T using bounded generation and then I will describe a
recent method based on the geometric properties of...
An XOR game is a very simple model of evaluating a distributed
function f(x,y) . With probability p(x,y) a Verifier sends
questions x, y to Alice and Bob, respectively. Without
communicating, Alice and Bob then output a, b in {-1,+1} in the
hope...
The PCP Theorem shows that any mathematical proof can be
efficiently converted into a form that can be checked
probabilistically by making only *two* queries to the proof, and
performing a "projection test" on the answers. This means that the
answer...
A PCP is a proof system in which the proofs that can be verified
by a verifier that reads only a very small part of the proof. One
line of research concerning PCPs is trying to reduce their
soundness error (i.e., the probability of accepting false...