On Dinur's proof of the PCP theorem

Authors:
Jaikumar Radhakrishnan and Madhu Sudan

Journal:
Bull. Amer. Math. Soc. **44** (2007), 19-61

MSC (2000):
Primary 68Q15, 68Q17, 68-02

Published electronically:
September 26, 2006

MathSciNet review:
2265009

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

**1.**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.**2.**N. Alon and V. D. Milman,*𝜆₁, isoperimetric inequalities for graphs, and superconcentrators*, J. Combin. Theory Ser. B**38**(1985), no. 1, 73–88. MR**782626**, 10.1016/0095-8956(85)90092-9**3.**N. Alon,*Eigenvalues and expanders*, Combinatorica**6**(1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR**875835**, 10.1007/BF02579166**4.**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****5.**S. Arora and C. Lund.

Hardness of approximations.

In D. S. Hochbaum, editor,*Approximation Algorithms for NP-Hard Problems*. PWS, 1995.**6.**Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy,*Proof verification and the hardness of approximation problems*, J. ACM**45**(1998), no. 3, 501–555. MR**1639346**, 10.1145/278298.278306**7.**Sanjeev Arora and Shmuel Safra,*Probabilistic checking of proofs: a new characterization of NP*, J. ACM**45**(1998), no. 1, 70–122. MR**1614328**, 10.1145/273865.273901**8.**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.**9.**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**, 10.1007/BF01200056**10.**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**, 10.1016/0022-0000(88)90028-1**11.**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**, 10.1109/18.556674**12.**Mihir Bellare, Oded Goldreich, and Madhu Sudan,*Free bits, PCPs, and nonapproximability—towards tight results*, SIAM J. Comput.**27**(1998), no. 3, 804–915 (electronic). MR**1612644**, 10.1137/S0097539796302531**13.**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.**14.**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.**15.**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**, 10.1145/1060590.1060631**16.**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**, 10.1016/0022-0000(93)90044-W**17.**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.**18.**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.**19.**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/`.**20.**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.**21.**Jozef Dodziuk,*Difference equations, isoperimetric inequality and transience of certain random walks*, Trans. Amer. Math. Soc.**284**(1984), no. 2, 787–794. MR**743744**, 10.1090/S0002-9947-1984-0743744-X**22.**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**, 10.1145/226643.226652**23.**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**, 10.1016/0304-3975(94)90251-8**24.**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**, 10.1137/0218012**25.**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.**26.**Johan Håstad,*Some optimal inapproximability results*, J. ACM**48**(2001), no. 4, 798–859. MR**2144931**, 10.1145/502090.502098**27.**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`.**28.**Russell Impagliazzo and David Zuckerman.

How to recycle random bits.

In*IEEE Symposium on Foundations of Computer Science*, pages 248-253, 1989.**29.**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****30.**L. A. Levin,*Universal enumeration problems*, Problemy Peredači Informacii**9**(1973), no. 3, 115–116 (Russian). MR**0340042****31.**Rajeev Motwani and Prabhakar Raghavan,*Randomized algorithms*, Cambridge University Press, Cambridge, 1995. MR**1344451****32.**Christos H. Papadimitriou and Mihalis Yannakakis,*Optimization, approximation, and complexity classes*, J. Comput. System Sci.**43**(1991), no. 3, 425–440. MR**1135471**, 10.1016/0022-0000(91)90023-X**33.**Ran Raz,*A parallel repetition theorem*, SIAM J. Comput.**27**(1998), no. 3, 763–803 (electronic). MR**1612640**, 10.1137/S0097539795280895**34.**J. T. Schwartz,*Fast probabilistic algorithms for verification of polynomial identities*, J. Assoc. Comput. Mach.**27**(1980), no. 4, 701–717. MR**594695**, 10.1145/322217.322225**35.**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`.**36.**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**

Retrieve articles in *Bulletin of the American Mathematical Society*
with MSC (2000):
68Q15,
68Q17,
68-02

Retrieve articles in all journals with MSC (2000): 68Q15, 68Q17, 68-02

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

DOI:
http://dx.doi.org/10.1090/S0273-0979-06-01143-8

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

Article copyright:
© Copyright 2006
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.