A WebPage on the PCP Theorem

by William Gasarch

(For now this is just papers that I want to gather in one place)

1. Probabilistic Checking of Proofs: A New Characterization of NP by Arora and Safra. AS.pdf JACM Vol 45, No 1, 70-122. 1998.

2. Proof Verification and Hardness of Approximation Problems by Arora, Lund, Motwani, Sudan, Szegedy. ALMSS.ps, ALMSS.pdf JACM Vol 45, No 3, 501-555, 1998.

3. Probabilistically Checkable Proofs and their Consequences for Approximation Algorithms by Hougardy, Promel, and Steger HRS.pdf

4. Lecture Notes on a small part of the theorem By Jon Katz. Katz.pdf

5. Robust PCP's of Proximity and Shorter PCP's PhD thesis by Prahladh Harsha. RobustPCP.pdf

6. Probablistic Checking of Proofs and Hardness of Approximation Problems PhD thesis by Sanjeev Arora. PCP-approx.pdf

7. The PCP Theorem by Gap Amplification by Irit Dinur. dinur.pdf

8. On Dinur's Proof of the PCP theorem by Jaikumar Radhakrishnan and Madhu Sudan. guide-dinur.pdf

9. The art of uninformed decisions: A primer to property testing by Eldar Fischer. Appeared in Computational Complexity Column of The Bulletin of the EACTC, vol 75, 2001, 97-126. Also in Current Trends in Computer Science: The challend of the New Century (edited by G. Paun, R. Rozenberg, and A. Salomaa) World Scientific Publishing (2004), Vol I, 229-264. proptesting.ps

10. Improved low degree testing by Arora and Sudan. STOC 1997. improved-low-degree-testing.pdf

11. Robust Characterization of Polynomials with Applications to Program Testing by Rubenfeld and Sudan. SICOMP 1996. robust-char-poly.ps, robust-char-poly.pdf