The PCP theorem
Séminaire Bourbaki : volume 2001/2002, exposés 894-908, Astérisque, no. 290 (2003), Exposé no. 895, 18 p. 
@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},
     series = {Ast\'erisque},
     note = {talk:895},
     pages = {19--36},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {290},
     year = {2003},
     mrnumber = {2074049},
     zbl = {02134849},
     language = {en},
     url = {http://www.numdam.org/item/SB_2001-2002__44__19_0/}
}
TY  - CHAP
AU  - Chazelle, Bernard
TI  - The PCP theorem
BT  - Séminaire Bourbaki : volume 2001/2002, exposés 894-908
AU  - Collectif
T3  - Astérisque
N1  - talk:895
PY  - 2003
SP  - 19
EP  - 36
IS  - 290
PB  - Société mathématique de France
UR  - http://www.numdam.org/item/SB_2001-2002__44__19_0/
LA  - en
ID  - SB_2001-2002__44__19_0
ER  - 
%0 Book Section
%A Chazelle, Bernard
%T The PCP theorem
%B Séminaire Bourbaki : volume 2001/2002, exposés 894-908
%A Collectif
%S Astérisque
%Z talk:895
%D 2003
%P 19-36
%N 290
%I Société mathématique de France
%U http://www.numdam.org/item/SB_2001-2002__44__19_0/
%G en
%F SB_2001-2002__44__19_0
Chazelle, Bernard. The PCP theorem, dans Séminaire Bourbaki : volume 2001/2002, exposés 894-908, Astérisque, no. 290 (2003), Exposé no. 895, 18 p. 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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

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

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

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

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

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

[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 | Zbl

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

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

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

[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 | Zbl

[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 | Zbl