Favorite Theorems: Probabilistically Checkable Proofs

April Edition

No single topic has dominated computational complexity over the past dozen years than probabilistically checkable proofs (PCPs). Arora, Lund, Motwani, Sudan and Szegedy, in a paper on my 1994 list, showed that every language in NP has a polynomial-sized PCP that can be verified by probabilistic polynomial-time verifier using O(log n) random coins and some constant number of queries. Well beyond the complexity interest in this result, PCPs give hardness of approximation results for a variety of NP-complete problems.

Researchers in many exciting papers have improved the parameters of the PCP results in order to get improved limits on approximation. But one paper really puts it all together for some tight results.

Some optimal inapproximability results by Johan Håstad, JACM, Volume 48, 2001.

Håstad's paper shows that every language L in NP has a PCP with with O(log n) random coins and 3 queries, where

1. If x is in L then the verifier is convinced with probability arbitrarily close to one.
2. If x is not in L then no proof can convince the verifier with probability more than one-half.

There parameters are the best possible.

The paper gives some optimal approximation results. Consider Max-3-SAT, where one wants to find an assignment that maximizes the number of satisfied clauses of a 3-CNF formula. We can satisfy 7/8 of the clauses by choosing a random assignment, a process we can also derandomize. Håstad's result implies that no better algorithm exists unless NP is easy. The paper also gives improved lower bounds on approximation on problems like vertex cover and max cut.

Håstad's paper pulls in tools from a large collection of research papers. Madhu Sudan's lecture notes describes Håstad's results and the techniques and papers leading up to it. There's also been exciting PCP research since Håstad's paper but I'll have to leave that for another day.