COSC85/185S96: Probabilistically Checkable Proofs
We presented a proof that languages in NP have (large!) probabilistically
checkable proofs of membership. Five pages of lecture notes are available.
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
MAX3SAT is not Capproximable in polytime for some constant C greater than 1
unless P=NP.
We also discussed gappreserving 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 NPhard problems,
D. Hochbaum editor,
PWS Publishing, 1996.
This is a survey which includes proofs of the basic nonapproximability
applications.
Misc. links:
 Mihir Bellare's PCP papers online
 10 papers (including seminal ones) on probabilistically checkable proofs.
 Crescenzi and Kann's compendium of approximation results.
 Like Garey & Johnson's NPhardness guide, except it covers *approximation*
problems and is available online. Look here for nonapproximability
results for your favorite problems.
 Robust Characterizations of Polynomials and Their Applications to
Program Testing, by Ronitt Rubinfeld and Madhu Sudan.
 On selftesting selfcorrecting programs, a building block for PCP's.

Nearly linearsize 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.
Last modified: Sat Nov 2 05:36:03 EST 2002
Neal Young <Neal.Young@dartmouth.edu>