** 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.