COSC85/185-S96: Probabilistically Checkable Proofs

We then showed how the stronger version of the PCP theorem in which the verifier uses only O(log(n)) random bits is equivalant to the fact that MAX-3SAT is not C-approximable in poly-time for some constant C greater than 1 unless P=NP. We also discussed gap-preserving reductions. Our reference for this part of the course is Hardness of approximations, by S. Arora and C. Lund, a chapter in the book Approximation Algorithms for NP-hard problems, D. Hochbaum editor, PWS Publishing, 1996. This is a survey which includes proofs of the basic non-approximability applications.

Misc. links:

Mihir Bellare's PCP papers on-line

10 papers (including seminal ones) on probabilistically checkable proofs.

Crescenzi and Kann's compendium of approximation results.

Like Garey & Johnson's NP-hardness guide, except it covers *approximation* problems and is available on-line. Look here for non-approximability results for your favorite problems.

Robust Characterizations of Polynomials and Their Applications to Program Testing, by Ronitt Rubinfeld and Madhu Sudan.

On self-testing self-correcting programs, a building block for PCP's.

Nearly linear-size holographic proofs, by Polishchuk and Spielman.

This work showed the existence of PCP's of size only slightly superlinear in the original proof size.

Probabilistic Checking of Proofs and Hardness of Approximation Problems (Contributed by Stavros.)

Indirect link to Sanjeev Arora's PhD thesis (1.2 Mb) -- a comprehensive exposition of the PCP theorem and its implications.