Joint Colloquium Distinguished Lecture Series
Hardness of Approximation and Probabilistically Checkable Proofs
 |
Wednesday, March 31, 2010 |
Abstract:
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, as well as some future directions. My past work includes showing exponential hardness for approximating constraint satisfaction problems even to within o(1), assuming it is exponentially hard to solve 3SAT exactly. This allows us to deduce exponential hardness with sharp thresholds for a multitude of approximation problems, and solve one of the field's long-standing open problems (joint work with Ran Raz).
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) might be helpful for proving the conjecture.
| Return to EECS Joint Colloquium |