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...
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...