COSC85/185-S96: 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
MAX-3SAT is not C-approximable in poly-time for some constant C greater than 1
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
Last modified: Sat Nov 2 05:36:03 EST 2002
Neal Young <Neal.Young@dartmouth.edu>
- 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
(Contributed by Stavros.)
- Indirect link to Sanjeev Arora's PhD thesis (1.2 Mb) -- a comprehensive
exposition of the PCP theorem and its implications.