@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 -
Chazelle, Bernard. The PCP theorem, in Séminaire Bourbaki : volume 2001/2002, exposés 894-908, Astérisque, no. 290 (2003), Talk no. 895, 18 p. http://www.numdam.org/item/SB_2001-2002__44__19_0/
[1] 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] Hardness of approximations, in Approximation Algorithms for NP-hard Problems (D. Hochbaum, ed.), PWS Publishing, 1996.
& -[3] Proof verification and the hardness of approximation problems, J. ACM 45 (1998), p. 501-555. | MR | Zbl
, , , & -[4] Probabilistic checking of proofs: a new characterization of NP, J. ACM 45 (1998), p. 70-122. | MR | Zbl
& -[5] Trading group theory for randomness, in Proc. 17th Annual ACM, Symp. Theory Comput., 1985, p. 421-429.
-[6] Checking computations in polylogarithmic time, in Proc. 23rd Annual ACM Symp. Theory Comput., 1991, p. 21-31.
, , & -[7] Non-deterministic exponential time has two-prover interactive protocols, Computational Complexity 1 (1991), p. 3-40. | MR | Zbl
, & -[8] Free bits, PCPs and nonapproximability-towards tight results, SIAM J. Comput. 27 (1998), p. 804-915. | MR | Zbl
, & -[9] Multi-prover interactive proofs: how to remove intractability, in Proc. 20th Annual ACM Symp. Theory Comput., 1988, p. 113-131.
, , & -[10] Designing programs that check their work, in Proc. 21st Annual ACM Symp. Theory Comput., 1989, p. 86-97.
& -[11] Self-testing/correcting with applications to numerical problems, J. Comp. Sys. Sci. 47 (1993), p. 549-595. | MR | Zbl
, & -[12] Theory of Computational Complexity, Wiley-Interscience, 2000. | MR | Zbl
& -[13] Interactive proofs and the hardness of approximating cliques, J. ACM 43 (1996), p. 268-292. | MR | Zbl
, , , & -[14] On the power of multi-prover interactive protocols, Theoret. Comput. Sci. 134 (1994), p. 545-557. | MR | Zbl
, & -[15] Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979. | MR | Zbl
& -[16] Self-testing/correcting for polynomials and approximate functions, in Proc. 23rd Annual ACM Symp. Theory Comput., 1991, p. 32-42.
, , , & -[17] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42 (1995), p. 1115-1145. | MR | Zbl
& -[18] Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Algorithms and Combinatorics, vol. 17, Springer, 1999. | MR | Zbl
-[19] 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] The knowledge complexity of interactive proof systems, SIAM J. Comput. 18 (1989), p. 186-208. | MR | Zbl
, & -[21] 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] 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] Algebraic methods for interactive proof systems, J. ACM 39 (1992), p. 859-868. | MR | Zbl
, , & -[25] Lectures on Proof Verification and Approximation Algorithms, LNCS, vol. 1367, Springer Verlag, 1998. | MR | Zbl
, & -[26] Computational Complexity, Addison Wesley, 1994. | MR | Zbl
-[27] A parallel repetition theorem, SIAM J. Comput. 27 (1998), p. 763-803. | MR | Zbl
-[28] 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] IP = PSPACE, J. ACM 39 (1992), p. 869-877. | MR | Zbl
-[31] Introduction to the Theory of Computation, PWS Publishing, 1997. | Zbl
-[32] Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems, in ACM Distinguished Dissertation Series for 1993, Springer, 1996. | MR | Zbl
-[33] Gadgets, Approximation, and Linear Programming, SIAM J. Comput. 29 (2000), p. 2074- 2097. | MR | Zbl
, , & -