Hardness of Approximation and Probabilistically Checkable Proofs
Speaker: Dana Moshkovitz , The Institute for Advanced Study
Date: March 15 2010
Time: 4:00PM to 5:00PM
Location: 32-G449
Host: Nancy Lynch, CSAIL
Contact: Francis Doughty, 253-4602, doughty@mit.edu
Relevant URL: 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.
Bio:
I am a member of the School of Mathematics in the Institute for Advanced Study. This is part of a post-doctoral fellowship joint with the Computer Science department of Princeton University, where I spent last year.
Prior to that I completed my PhD at the Weizmann Institute in Israel.
I have a broad interest in Theoretical Computer Science, and especially in probabilistically checkable proofs (PCP), pseudo-randomness and coding theory.
See other events that are part of CS Special Seminar Series Spring 2010
See other events happening in March 2010
