PCP Links

Probabilistically Checkable Proofs and Approximation

Background The NP-completeness of important optimization problems focused research effort on the design of approximation algorithms. Some problems succumbed to approximation. Others, however defied all efforts to either find good approximation algorithms or to show such algorithms don't exist. A breakthrough came in a 1991 paper by Feige, Goldwasser, Lovasz, Safra, and Szegedy. They used results on probabilistically checkable proofs (PCPs) to show that Max Clique is hard to approximate. Research has since then expanded to apply their approach to other problems, and to improve the results. Today, the known results are quite amazingly broad and strong, and research is still advancing rapidly.

Pointers Over the past few years, much has been written on this subject. Below are pointers to some relevant survey articles and their authors. Clicking on the article name typically brings up a postscript file, or, if one is not available, information on the best source I know to get the article. Comments and pointers to additional sources appreciated.

S. Arora. Probabilistic Checking of Proofs and Hardness of Approximation Problems, 1995. A technical report based on the author's Ph.D thesis. Contains a proof of the PCP theorem.
S. Arora and C. Lund. Hardness of approximations. Chapter in the book Approximation Algorithms for NP-hard problems, D. Hochbaum editor, PWS Publishing, 1996. A survey which includes proofs of the basic non-approximability applications.
L. Babai. Transparent Proofs and Limits to Approximation, 1994. A survey on proof checking and its applications to obtaining non-approximability results. An earlier version appeared in the Proceedings of the first European Congress of Mathematics, Eds. A. Joseph, F. Mignot, F. Murat, B. Prum and R. Rentschaler, Springer, Berlin, 1994.
M. Bellare. Proof Checking and Approximation: Towards Tight Results, 1996. Slightly expanded version of a survey that appears in the Complexity Theory Column of Sigact News, Vol. 27, No. 1, March 1996. It describes recent developments, stating the best known non-approximability results and explaining how they are being derived. Hope to keep it up to date.
P. Crescenzi and V. Kann. A compendium of NP optimization problems, 1996. A comprehensive summary of the current approximability status of over 150 optimization problems. Indicates, for each problem, both the factor achieved by the best known approximation algorithm and the best known hardness result, with references to the relevant sources.
U. Feige and S. Goldwasser. A Report on the 1994 Weizmann Workshop on Probabilistic Proof Systems, 1994. Contains abstracts of the presentations at the workshop and a bibliography of papers on approximation, probabilistically checkable proofs, and non-approximability up to early 1994.
O. Goldreich. Probabilistic proof systems, a survey, December 1996. An introduction to the area of proof systems. While PCP is not the main theme, this is a very useful and readable general introduction to the broader area of probabilistic proofs.
V. Heun, W. Merkle and U. Weigand. Proving the PCP theorem. Lectures on Proof Verification and Approximation Algorithms, E. Mayr, H. Promel, A. Steger, editors, Lecture Notes in Computer Science Vol. 1367, Springer, 1998, pages 83-160.
S. Hougardy, H. Proemel, and A. Steger. Probabilistically Checkable Proofs and their Consequences for Approximation Algorithms. Discrete Mathematics 136, 1994. Contains a proof of the PCP theorem.
D. Johnson. The tale of the second prover. In the NP-completeness column: an on-going guide, J. of Algorithms, Vol. 13, No. 3, pp. 502--524, 1992.
V. Kann and A. Panconesi. Hardness of approximation, 1996. To appear in Annoted bibliographies in combinatorial optimization.
D. Shmoys. Computing near-optimal solutions to combinatorial optimization problems. Chapter in the book Combinatorial Optimization, DIMACS series in Discrete Mathematics and Theoretical Computer Science Vol. 20, W. Cook, L. Lovasz, and P. Seymour editors, AMS, 1995. A survey of approximation algorithms for combinatorial optimization problems.
M. Sudan. Efficient checking of polynomials and proofs, and the hardness of approximation problems. Ph. D thesis, UC Berkeley, 1992, updated and published in ACM Distinguished Theses series, Lecture Notes in Computer Science Vol. 1001, Springer, 1996. Contains a proof of the PCP theorem.
M. Sudan. On the role of algebra in the efficient verification of proofs, 1995. A short article about the error-correcting codes viewpoint which underlies the constructions of efficiently checkable proofs.