Probabilistically Checkable Proofs and Approximation
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.
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
- 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
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
- 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
- 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,
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
- 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,
A survey of approximation algorithms for combinatorial optimization
- 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.