The PCP theorem
Séminaire Bourbaki : volume 2001/2002, exposés 894-908, Astérisque no. 290  (2003), Talk no. 895, p. 19-36
@incollection{SB_2001-2002__44__19_0,
     author = {Chazelle, Bernard},
     title = {The PCP theorem},
     booktitle = {S\'eminaire Bourbaki : volume 2001/2002, expos\'es 894-908},
     author = {Collectif},
     series = {Ast\'erisque},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {290},
     year = {2003},
     note = {talk:895},
     pages = {19-36},
     zbl = {02134849},
     mrnumber = {2074049},
     language = {en},
     url = {http://www.numdam.org/item/SB_2001-2002__44__19_0}
}
Chazelle, Bernard. The PCP theorem, in Séminaire Bourbaki : volume 2001/2002, exposés 894-908, Astérisque, no. 290 (2003), Talk no. 895, pp. 19-36. http://www.numdam.org/item/SB_2001-2002__44__19_0/

[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] S. Arora & C. Lund - Hardness of approximations, in Approximation Algorithms for NP-hard Problems (D. Hochbaum, ed.), PWS Publishing, 1996.

[3] S. Arora, C. Lund, R. Motwani, M. Sudan & M. Szegedy - Proof verification and the hardness of approximation problems, J. ACM 45 (1998), p. 501-555. | MR 1639346 | Zbl 1065.68570

[4] S. Arora & M. Safra - Probabilistic checking of proofs: a new characterization of NP, J. ACM 45 (1998), p. 70-122. | MR 1614328 | Zbl 0903.68076

[5] L. Babai - Trading group theory for randomness, in Proc. 17th Annual ACM, Symp. Theory Comput., 1985, p. 421-429.

[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] L. Babai, L. Fortnow & C. Lund - Non-deterministic exponential time has two-prover interactive protocols, Computational Complexity 1 (1991), p. 3-40. | MR 1113533 | Zbl 0774.68041

[8] M. Bellare, O. Goldreich & M. Sudan - Free bits, PCPs and nonapproximability-towards tight results, SIAM J. Comput. 27 (1998), p. 804-915. | MR 1612644 | Zbl 0912.68041

[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] M. Blum & S. Kannan - Designing programs that check their work, in Proc. 21st Annual ACM Symp. Theory Comput., 1989, p. 86-97.

[11] M. Blum, M. Luby & R. Rubinfeld - Self-testing/correcting with applications to numerical problems, J. Comp. Sys. Sci. 47 (1993), p. 549-595. | MR 1248868 | Zbl 0795.68131

[12] D.-Z. Du & K.-I. Ko - Theory of Computational Complexity, Wiley-Interscience, 2000. | MR 1789501 | Zbl 1001.68050

[13] U. Feige, S. Goldwasser, L. Lovasz, S. Safra & M. Szegedy - Interactive proofs and the hardness of approximating cliques, J. ACM 43 (1996), p. 268-292. | MR 1408323 | Zbl 0882.68129

[14] L. Fortnow, J. Rompel & M. Sipser - On the power of multi-prover interactive protocols, Theoret. Comput. Sci. 134 (1994), p. 545-557. | MR 1304678 | Zbl 0938.68824

[15] M. Garey & D. Johnson - Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979. | MR 519066 | Zbl 0411.68039

[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] M. X. Goemans & D. P. Williamson - Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42 (1995), p. 1115-1145. | MR 1412228 | Zbl 0885.68088

[18] O. Goldreich - Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Algorithms and Combinatorics, vol. 17, Springer, 1999. | MR 1665938 | Zbl 0907.94002

[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. ACM 38 (1991), p. 691-729. | MR 1125927 | Zbl 0799.68101

[20] S. Goldwasser, S. Micali & C. Rackoff - The knowledge complexity of interactive proof systems, SIAM J. Comput. 18 (1989), p. 186-208. | MR 978174 | Zbl 0677.68062

[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] 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. | MR 1715618 | Zbl 0963.68193

[23] _, Clique is hard to approximate within n1-∈, Acta Mathematica 182 (1999), p. 105-142. | Zbl 0989.68060

[24] C. Lund, L. Fortnow, H. Karloff & N. Nisan - Algebraic methods for interactive proof systems, J. ACM 39 (1992), p. 859-868. | MR 1187215 | Zbl 0799.68097

[25] E. W. Mayr, H. J. Promel & A. Steger - Lectures on Proof Verification and Approximation Algorithms, LNCS, vol. 1367, Springer Verlag, 1998. | MR 1640479 | Zbl 1043.68579

[26] C. H. Papadimitriou - Computational Complexity, Addison Wesley, 1994. | MR 1251285 | Zbl 0833.68049

[27] R. Raz - A parallel repetition theorem, SIAM J. Comput. 27 (1998), p. 763-803. | MR 1612640 | Zbl 0911.68082

[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. | MR 1173877 | Zbl 0834.68076

[29] _, Robust characterizations of polynomials with applications to program testing, SIAM J. Comput. 25 (1996), p. 252-271. | MR 1379300 | Zbl 0844.68062

[30] A. Shamir - IP = PSPACE, J. ACM 39 (1992), p. 869-877. | MR 1187216 | Zbl 0799.68096

[31] M. Sipser - Introduction to the Theory of Computation, PWS Publishing, 1997. | Zbl 1169.68300

[32] M. Sudan - Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems, in ACM Distinguished Dissertation Series for 1993, Springer, 1996. | MR 1442261 | Zbl 0861.68042

[33] L. Trevisan, G. B. Sorkin, M. Sudan & D. P. Williamson - Gadgets, Approximation, and Linear Programming, SIAM J. Comput. 29 (2000), p. 2074- 2097. | MR 1756405 | Zbl 0957.68048