The PCP theorem

 Access to full text

 Full (PDF)

1. [1] S. Arora — Probabilistic Checking of Proofs and the Hardness of Approximation Problems, Ph.D. Thesis, UC Berkeley, 1994, also available as http://www.cs.princeton.edu/~arora. 
2. [2] S. Arora & C. Lund — Hardness of approximations, in Approximation Algorithms for NP-hard Problems (D. Hochbaum, ed.), PWS Publishing, 1996. 
3. [3] S. Arora, C. Lund, R. Motwani, M. Sudan & M. Szegedy - Proof verification and the hardness of approximation problems, J. ACM45 (1998), p. 501-555. Zbl1065.68570MR1639346
4. [4] S. Arora & M. Safra — Probabilistic checking of proofs: a new characterization of NP, J. ACM45 (1998), p. 70-122. Zbl0903.68076MR1614328
5. [5] L. Babai — Trading group theory for randomness, in Proc. 17th Annual ACM, Symp. Theory Comput., 1985, p. 421-429. 
6. [6] L. Babai, L. Fortnow, L. Levin & M. Szegedy — Checking computations in polylogarithmic time, in Proc. 23rd Annual ACM Symp. Theory Comput., 1991, p. 21-31. 
7. [7] L. Babai, L. Fortnow & C. Lund — Non-deterministic exponential time has two-prover interactive protocols, Computational Complexity1 (1991), p. 3-40. Zbl0774.68041MR1113533
8. [8] M. Bellare, O. Goldreich & M. Sudan - Free bits, PCPs and nonapproximability—towards tight results, SIAM J. Comput.27 (1998), p. 804-915. Zbl0912.68041MR1612644
9. [9] M. Ben-Or, S. Goldwasser, J. Kilian & A. Wigderson — Multi-prover interactive proofs: how to remove intractability, in Proc. 20th Annual ACM Symp. Theory Comput., 1988, p. 113-131. 
10. [10] M. Blum & S. Kannan — Designing programs that check their work, in Proc. 21st Annual ACM Symp. Theory Comput., 1989, p. 86-97. Zbl0886.68046
11. [11] M. Blum, M. Luby & R. Rubinfeld — Self-testing/correcting with applications to numerical problems, J. Comp. Sys. Sci.47 (1993), p. 549-595. Zbl0795.68131MR1248868
12. [12] D.-Z. Du & K.-I. Ko - Theory of Computational Complexity, Wiley-Interscience, 2000. Zbl1001.68050MR1789501
13. [13] U. Feige, S. Goldwasser, L. Lovasz, S. Safra & M. Szegedy - Interactive proofs and the hardness of approximating cliques, J. ACM43 (1996), p. 268-292. Zbl0882.68129MR1408323
14. [14] L. Fortnow, J. Rompel & M. Sipser — On the power of multi-prover interactive protocols, Theoret. Comput. Sci.134 (1994), p. 545-557. Zbl0938.68824MR1304678
15. [15] M. Garey & D. Johnson — Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979. Zbl0411.68039MR519066
16. [16] P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan & A. Wigderson - Self-testing/correcting for polynomials and approximate functions, in Proc. 23rd Annual ACM Symp. Theory Comput., 1991, p. 32-42. 
17. [17] M.X. Goemans & D.P. Williamson — Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM42 (1995), p. 1115-1145. Zbl0885.68088MR1412228
18. [18] O. Goldreich — Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Algorithms and Combinatorics, vol. 17, Springer, 1999. Zbl0907.94002MR1665938
19. [19] O. Goldreich, S. Micali & A. Wigderson — Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, J. ACM38 (1991), p. 691-729. Zbl0799.68101MR1125927
20. [20] S. Goldwasser, S. Micali & C. Rackoff — The knowledge complexity of interactive proof systems, SIAM J. Comput.18 (1989), p. 186-208. Zbl0677.68062MR978174
21. [21] V. Guruswami, D. Lewin, M. Sudan & L. Trevisan — A tight characterization of NP with 3 query PCPs, in Proc. 39th Annual IEEE Symp. Found. Comput. Sci., 1998, also available as ECCC Technical Report TR98-034, p. 8-17. 
22. [22] J. Håstad — Some optimal inapproximability results, in Proc. 29th Annual ACM Symp. Theory Comput., 1997, also available as ECCC Technical Report TR97- 037, p. 1-10. Zbl0963.68193MR1715618
23. [23] _, Clique is hard to approximate within n1-∈, Acta Mathematica182 (1999), p. 105-142. Zbl0989.68060
24. [24] C. Lund, L. Fortnow, H. Karloff & N. Nisan — Algebraic methods for interactive proof systems, J. ACM39 (1992), p. 859-868. Zbl0799.68097MR1187215
25. [25] E.W. Mayr, H.J. Promel & A. Steger — Lectures on Proof Verification and Approximation Algorithms, LNCS, vol. 1367, Springer Verlag, 1998. Zbl1043.68579MR1640479
26. [26] C.H. Papadimitriou — Computational Complexity, Addison Wesley, 1994. Zbl0833.68049MR1251285
27. [27] R. Raz — A parallel repetition theorem, SIAM J. Comput.27 (1998), p. 763-803. Zbl0911.68082MR1612640
28. [28] R. Rubinfeld & M. Sudan - Self-testing polynomial functions efficiently and over rational Domains, in Proc. 3rd Annual ACM/SIAM Symp. Discrete Algorithms, 1992, p. 23-32. Zbl0834.68076MR1173877
29. [29] _, Robust characterizations of polynomials with applications to program testing, SIAM J. Comput.25 (1996), p. 252-271. Zbl0844.68062MR1379300
30. [30] A. Shamir — IP = PSPACE, J. ACM39 (1992), p. 869-877. Zbl0799.68096MR1187216
31. [31] M. Sipser — Introduction to the Theory of Computation, PWS Publishing, 1997. Zbl1169.68300
32. [32] M. Sudan - Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems, in ACM Distinguished Dissertation Series for 1993, Springer, 1996. Zbl0861.68042MR1442261
33. [33] L. Trevisan, G.B. Sorkin, M. Sudan & D.P. Williamson — Gadgets, Approximation, and Linear Programming, SIAM J. Comput.29 (2000), p. 2074- 2097. Zbl0957.68048MR1756405