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...
We present two new approximation algorithms for Unique Games.
The first generalizes the results of Arora et al. who give
polynomial time approximation algorithms for graphs with high
conductance. We give a polynomial time algorithm assuming
only...
We present two new approximation algorithms for Unique Games.
The first generalizes the results of Arora et al. who give
polynomial time approximation algorithms for graphs with high
conductance. We give a polynomial time algorithm assuming
only...
We present a gap theorem regarding the complexity of the circuit
satisfiability problem.
We prove that the success probability of deciding Circuit
Satisfiability for deterministic
circuits with n variables and size m is either
2−n or 2−o(n) when...
In his seminal work, Valiant defined algebraic analogs for the
classes P and NP, which are known today as VP and VNP. He also
showed that the permanent is VNP-complete (that is, the permanent
is in VNP and any problem in VNP is reducible to it). We...
Constraint Satisfaction Problems appear everywhere. The study of
their quantum analogues (in which the constraints no longer
commute), has become a lively area of study, and various recent
results provide interesting insights into quantum physics...
The general adversary bound is a lower bound on the number of
input queries required for a quantum algorithm to evaluate a
boolean function. We show that this lower bound is in fact tight,
up to a logarithmic factor. The proof is based on span...
