Computer Science Colloquium
Thursday, March 6, 2003
4:15 PM
B17 Upson Hall

Subhash Khot
Princeton University


Probabilistically Checkable Proofs (PCPs) and Hardness of Approximation

     Computing approximate solutions is a way to cope with  NP-complete  problems.  For some problems however,  it can be proved that computing  even approximate solutions is NP-hard. A tool called Probabilistically  Checkable Proofs (PCPs) is used extensively to establish such results,  commonly  known as  hardness of approximation results.   PCPs  give an  alternate definition of NP as the class of languages having membership  proofs  that can be "spot-checked" by  a probabilistic  verifier.  The  verifier  needs to read only a constant number of bits  from the proof  and uses only a limited amount of randomness.  My  work continues this  line of research and I obtain (sometimes with co-authors) new hardness  results for (1) Graph and Hypergraph Coloring (2) Vertex Cover in Hyper- graphs  (3)  Constraint  Satisfaction  Problems  (4)  Clique-size  and  Chromatic Number of Graphs (5) the Shortest Vector Problem in lattices.

     In this talk, I will give a survey of PCPs, known hardness results,  techniques used to build PCPs and some of my work. The talk will be self-contained.