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), 19-61 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/0095-8956(85)90092-9
- 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, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1992. With an appendix by Paul Erdős; A Wiley-Interscience Publication. MR 1140703 AroraLund S. Arora and C. Lund. Hardness of approximations. In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard 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 two-prover interactive protocols, Comput. Complexity 1 (1991), no. 1, 3–40. MR 1113533, DOI 10.1007/BF01200056
- László Babai and Shlomo Moran, Arthur-Merlin 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/0022-0000(88)90028-1
- 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. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs: How to remove intractability. In Proceedings of the 20th Annual ACM Symposium on the Theory of Computing, pages 113–131, 1988.
- Eli Ben-Sasson and Madhu Sudan, Simple PCPs with poly-log 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, Self-testing/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/0022-0000(93)90044-W 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 theorem-proving 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 TR05-046, ECCC, 2005. Revision 1, available from http://eccc.uni-trier.de/eccc-reports/2005/TR05-046/. IritOmer Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP-theorem. 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/S0002-9947-1984-0743744-X
- 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 multi-prover interactive protocols, Theoret. Comput. Sci. 134 (1994), no. 2, 545–557. MR 1304678, DOI 10.1016/0304-3975(94)90251-8
- 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 3-query PCPs. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pages 8–17, Palo Alto, California, 8-11 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/0022-0000(91)90023-X
- 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:pcp-slides Madhu Sudan. PCP and inapproximability: Survey and open problems, February 2000. Slides of talk given at DIMACS Workshop on Approximability of NP-Hard 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, Berlin-New 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, 32-G640, 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 CCR-0312575. 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), 19-61
- MSC (2000): Primary 68Q15, 68Q17, 68-02
- DOI: https://doi.org/10.1090/S0273-0979-06-01143-8
- MathSciNet review: 2265009