Dana Moshkovitz

Institute for Advanced Studies

One of the greatest achievements of Theoretical Computer Science was to show NP-hardness of *approximation* problems. This required a new, surprising understanding about the power of NP: All NP problems have proofs that can be checked probabilistically by reading only a *constant* number of proof symbols. This Theorem became known as the PCP Theorem (PCP stands for Probabilistically Checkable Proofs).

In the talk I will describe my past and present work in the field.This includes constructing short PCPs with vanishing error, and proving the hardness of projection games for vanishing error
(joint work with Ran Raz). Projection games are a special kind of PCPs. They serve as the basis
of almost all NP-hardness of approximation results.  Proving the NP-hardness of projection games with vanishing error has been one of the field's long-lasting open problems.

I will also describe the fruits of a recent exploration (joint with Subhash Khot) of another notorious open problem, the Unique Games Conjecture (UGC). We pose a new problem, called Robust-3LIN(R), about the approximate satisfiability of homogeneous linear equations over the reals. We show that a proof for the UGC will imply NP-hardness of approximating Robust-3LIN(R). We believe that proving the NP-hardness of approximating Robust-3LIN(R) directly *might* be helpful for proving the conjecture.


B17 Upson Hall

Thursday, March 11, 2010

Refreshments at 3:45pm in the Upson 4th Floor Atrium


Computer Science


Spring 2010


Hardness of Approximation

and Probabalistically Checkable Proofs