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.