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 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...
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...
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...
An affine disperser over F2n for sources of dimension d is a
function f: F2n --> F2 such that for any affine subspace S in
F2n of dimension at least d, we have {f(s) : s in S} = F2 . Affine
dispersers have been considered in the context of...
We prove that every graph has a spectral sparsifier with a
number of edges linear in its
number of vertices. As linear-sized spectral sparsifiers of
complete graphs are expanders, our
sparsifiers of arbitrary graphs can be viewed as
generalizations...
For the past decade, the Institute’s Science Initiative Group
(SIG) has worked with the World Bank and other partners to
strengthen science in developing nations. In this talk, Phillip
Griffiths, who helped create SIG when he was Director of the...
A five day workshop focusing on the theory of nonlinear PDEs and
their applications to problems in geometry. Topics include
conformal geometry, mass transportation, and free boundary...
