Hardness of Approximation Results
Subhash Khot, Georgia Institute of Technology
Thursday, 28 April, 10:00AM, 3305 NSH

Abstract:

Computing approximate solutions is a natural way to cope with NP-completeness. However, for many NP-complete problems, computing even approximate solutions can be shown to be a "hard" problem. Such hardness results have several motivations arising from algorithm design, complexity theory, cryptography and many areas in mathematics, including Fourier analysis and metric embeddings.

Surprisingly, these hardness results are intimately related to constructing proofs for NP-statements that can be "spot-checked" efficiently. A celebrated result called the PCP Theorem gives a way of writing a "short" proof for any NP-statement, which a probabilistic verifier can verify by reading only a constant(!) number of locations in the proof. Apart from their application to hardness results, PCP techniques have found wide applicability in theoretical computer science.

I will give an overview of my research on hardness results, along with a brief introduction to probabilistically checkable proofs.

Subhash Khot received his PhD in Computer Science from Princeton University in 2003. He spent 2003-2004 at the Institute for Advanced Studies. He is now an assistant professor at the Georgia Institute of Technology.