On Dinur’s proof of the PCP theorem
HTML articles powered by AMS MathViewer
 by Jaikumar Radhakrishnan and Madhu Sudan PDF
 Bull. Amer. Math. Soc. 44 (2007), 1961 Request permission
Abstract:
Probabilistically checkable proofs are proofs that can be checked probabilistically by reading very few bits of the proof. In the early 1990s, it was shown that proofs could be transformed into probabilistically checkable ones with only a modest increase in their length. The initial transformations, though elementary, were a little too complex. A recent work due to Irit Dinur gives a dramatically simple (and radically new) construction of probabilistically checkable proofs. This article explains the notion of a probabilistically checkable proof, presents the formal definition and then introduces the reader to Dinur’s work along with some of the context.References

AKS M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in logspace. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 132–140, 1987.
 N. Alon and V. D. Milman, $\lambda _1,$ isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73–88. MR 782626, DOI 10.1016/00958956(85)900929
 N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR 875835, DOI 10.1007/BF02579166
 Noga Alon and Joel H. Spencer, The probabilistic method, WileyInterscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1992. With an appendix by Paul Erdős; A WileyInterscience Publication. MR 1140703 AroraLund S. Arora and C. Lund. Hardness of approximations. In D. S. Hochbaum, editor, Approximation Algorithms for NPHard Problems. PWS, 1995.
 Sanjeev Arora and Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, J. ACM 45 (1998), no. 1, 70–122. MR 1614328, DOI 10.1145/273865.273901
 Sanjeev Arora and Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, J. ACM 45 (1998), no. 1, 70–122. MR 1614328, DOI 10.1145/273865.273901 BFLS László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd ACM Symposium on the Theory of Computing, pages 21–32. ACM, New York, 1991.
 László Babai, Lance Fortnow, and Carsten Lund, Nondeterministic exponential time has twoprover interactive protocols, Comput. Complexity 1 (1991), no. 1, 3–40. MR 1113533, DOI 10.1007/BF01200056
 László Babai and Shlomo Moran, ArthurMerlin games: a randomized proof system, and a hierarchy of complexity classes, J. Comput. System Sci. 36 (1988), no. 2, 254–276. 17th Annual ACM Symposium on the Theory of Computing (Providence, RI, 1985). MR 950433, DOI 10.1016/00220000(88)900281
 Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos Kiwi, and Madhu Sudan, Linearity testing in characteristic two, IEEE Trans. Inform. Theory 42 (1996), no. 6, 1781–1795. Codes and complexity. MR 1465738, DOI 10.1109/18.556674
 Mihir Bellare, Oded Goldreich, and Madhu Sudan, Free bits, PCPs, and nonapproximability—towards tight results, SIAM J. Comput. 27 (1998), no. 3, 804–915. MR 1612644, DOI 10.1137/S0097539796302531 BGLR Mihir Bellare, Shafi Goldwasser, Carsten Lund, and Alex Russell. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the 25th ACM Symposium on the Theory of Computing, pages 294–304. ACM, New York, 1993. BGKW M. BenOr, S. Goldwasser, J. Kilian, and A. Wigderson. Multiprover interactive proofs: How to remove intractability. In Proceedings of the 20th Annual ACM Symposium on the Theory of Computing, pages 113–131, 1988.
 Eli BenSasson and Madhu Sudan, Simple PCPs with polylog rate and query complexity, STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 266–275. MR 2181626, DOI 10.1145/1060590.1060631
 Manuel Blum, Michael Luby, and Ronitt Rubinfeld, Selftesting/correcting with applications to numerical problems, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), 1993, pp. 549–595. MR 1248868, DOI 10.1016/00220000(93)90044W CW Aviad Cohen and Avi Wigderson. Dispersers, deterministic amplification, and weak random sources (extended abstract). In IEEE Symposium on Foundations of Computer Science, pages 14–19, 1989. Cook Stephen A. Cook. The complexity of theoremproving procedures. In Proceedings of the 3rd ACM Symposium Theory of Computing, pages 151–158, Shaker Heights, Ohio, 1971. Dinur Irit Dinur. The PCP theorem by gap amplification. Technical Report TR05046, ECCC, 2005. Revision 1, available from http://eccc.unitrier.de/ecccreports/2005/TR05046/. IritOmer Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCPtheorem. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages 155–164, 2004.
 Jozef Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787–794. MR 743744, DOI 10.1090/S0002994719840743744X
 Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy, Interactive proofs and the hardness of approximating cliques, J. ACM 43 (1996), no. 2, 268–292. MR 1408323, DOI 10.1145/226643.226652
 Lance Fortnow, John Rompel, and Michael Sipser, On the power of multiprover interactive protocols, Theoret. Comput. Sci. 134 (1994), no. 2, 545–557. MR 1304678, DOI 10.1016/03043975(94)902518
 Shafi Goldwasser, Silvio Micali, and Charles Rackoff, The knowledge complexity of interactive proof systems, SIAM J. Comput. 18 (1989), no. 1, 186–208. MR 978174, DOI 10.1137/0218012 GLST Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, and Luca Trevisan. A tight characterization of NP with 3query PCPs. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pages 8–17, Palo Alto, California, 811 November 1998.
 Johan Håstad, Some optimal inapproximability results, J. ACM 48 (2001), no. 4, 798–859. MR 2144931, DOI 10.1145/502090.502098 HLW:article Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the AMS, 43(4):439–561, October 2006. Full version available from http://www.math.ias.edu/~avi/BOOKS/expanderbookr1.pdf. IZ Russell Impagliazzo and David Zuckerman. How to recycle random bits. In IEEE Symposium on Foundations of Computer Science, pages 248–253, 1989.
 Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 85–103. MR 0378476
 L. A. Levin, Universal enumeration problems, Problemy Peredači Informacii 9 (1973), no. 3, 115–116 (Russian). MR 0340042
 Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, Cambridge, 1995. MR 1344451, DOI 10.1017/CBO9780511814075
 Christos H. Papadimitriou and Mihalis Yannakakis, Optimization, approximation, and complexity classes, J. Comput. System Sci. 43 (1991), no. 3, 425–440. MR 1135471, DOI 10.1016/00220000(91)90023X
 Ran Raz, A parallel repetition theorem, SIAM J. Comput. 27 (1998), no. 3, 763–803. MR 1612640, DOI 10.1137/S0097539795280895
 J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. MR 594695, DOI 10.1145/322217.322225 madhu:pcpslides Madhu Sudan. PCP and inapproximability: Survey and open problems, February 2000. Slides of talk given at DIMACS Workshop on Approximability of NPHard Problems, Nassau Inn, Princeton, NJ. Available from http://theory.csail.mit.edu/~madhu/slides/dimacs00.ps.
 Richard Zippel, Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, BerlinNew York, 1979, pp. 216–226. MR 575692
Additional Information
 Jaikumar Radhakrishnan
 Affiliation: School of Technology and Computer Science, Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai 400005, India
 Email: jaikumar@tifr.res.in
 Madhu Sudan
 Affiliation: CS & AI Laboratory (CSAIL), Massachusetts Institute of Technology, 32G640, 32 Vassar Street, Cambridge, Massachusetts 02139
 Received by editor(s): August 2, 2006
 Published electronically: September 26, 2006
 Additional Notes: This article is based on a lecture presented January 14, 2006, at the AMS Special Session on Current Events, Joint Mathematics Meetings, San Antonio, TX
This article was written while the first author was visiting the Toyota Technological Institute at Chicago
The second author was supported in part by NSF Award CCR0312575. Views expressed in this article are those of the authors and are not endorsed by the NSF  © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.  Journal: Bull. Amer. Math. Soc. 44 (2007), 1961
 MSC (2000): Primary 68Q15, 68Q17, 6802
 DOI: https://doi.org/10.1090/S0273097906011438
 MathSciNet review: 2265009