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...
This series of three talks will give a nontechnical, high level
overview of geometric complexity theory (GCT), which is an approach
to the P vs. NP problem via algebraic geometry, representation
theory, and the theory of a new class of quantum...