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

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

Published electronically:
September 26, 2006

MathSciNet review:
2265009

Full-text PDF Free Access

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.*Journal of Combinatorial Theory, Series B*, 38(1):73-88, 1985. MR**0782626 (87b:05092)****3.**Noga Alon.

Eigenvalues and expanders.*Combinatorica*, 6:83-96, 1986. MR**0875835 (88e:05077)****4.**Noga Alon and Joel Spencer.*The Probabilistic Method*.

John Wiley and Sons, Inc., 1992. MR**1140703 (93h:60002)****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.*Journal of the ACM*, 45(3):501-555, May 1998. MR**1639346 (99d:68077b)****7.**Sanjeev Arora and Shmuel Safra.

Probabilistic checking of proofs: A new characterization of NP.*Journal of the ACM*, 45(1):70-122, January 1998. MR**1614328 (99d:68077a)****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.

Non-deterministic exponential time has two-prover interactive protocols.*Computational Complexity*, 1(1):3-40, 1991. MR**1113533 (92h:68031)****10.**László Babai and Shlomo Moran.

Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class.*Journal of Computer and System Sciences*, 36(2):254-276, April 1988. MR**0950433 (90b:68028)****11.**Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos Kiwi, and Madhu Sudan.

Linearity testing over characteristic two.*IEEE Transactions on Information Theory*, 42(6):1781-1795, November 1996. MR**1465738 (98m:68111)****12.**Mihir Bellare, Oded Goldreich, and Madhu Sudan.

Free bits, PCP's and non-approximability -- towards tight results.*SIAM Journal on Computing*, 27(3):804-915, 1998. MR**1612644 (2000a:68034)****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.

Short PCPs with poly-log rate and query complexity.

In*Proceedings of the 37th Annual ACM Symposium on Theory of Computing*, pages 266-275, 2005. MR**2181626 (2006g:68066)****16.**Manuel Blum, Michael Luby, and Ronitt Rubinfeld.

Self-testing/correcting with applications to numerical problems.*Journal of Computer and System Sciences*, 47(3):549-595, 1993. MR**1248868 (94m:65020)****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.**J. Dodziuk.

Difference equations, isoperimetric inequalities, and transience of certain random walks.*Transactions of the American Mathematical Society*, 284(2):787-794, 1984. MR**0743744 (85m:58185)****22.**Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy.

Interactive proofs and the hardness of approximating cliques.*Journal of the ACM*, 43(2):268-292, 1996. MR**1408323 (97h:68037)****23.**Lance Fortnow, John Rompel, and Michael Sipser.

On the power of multi-prover interactive protocols.*Theoretical Computer Science*, 134(2):545-557, 1994. MR**1304678 (95k:68047)****24.**Shafi Goldwasser, Silvio Micali, and Charles Rackoff.

The knowledge complexity of interactive proof systems.*SIAM Journal on Computing*, 18(1):186-208, February 1989. MR**0978174 (90f:68157)****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.*Journal of the ACM*, 48:798-859, 2001. MR**2144931 (2006c:68066)****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*(R. Miller and J. Thatcher, eds.), pages 85-103, 1972. MR**0378476 (51:14644)****30.**Leonid A. Levin.

Universal search problems.*Problemy Peredachi Informatsii*, 9(3):265-266, 1973. MR**0340042 (49:4799)****31.**Rajeev Motwani and Prabhakar Raghavan.*Randomized Algorithms*.

Cambridge University Press, 1995. MR**1344451 (96i:65003)****32.**C. H. Papadimitriou and M. Yannakakis.

Optimization, approximation, and complexity classes.*Journal of Computer and System Sciences*, 43:425-440, 1991. MR**1135471 (93e:68027)****33.**Ran Raz.

A parallel repetition theorem.*SIAM Journal on Computing*, 27(3):763-803, 1998. MR**1612640 (2000c:68057)****34.**J. T. Schwartz.

Fast probabilistic algorithms for verification of polynomial identities.*Journal of the ACM*, 27(4):701-717, October 1980. MR**0594695 (82m:68078)****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 E. Zippel.

Probabilistic algorithms for sparse polynomials.

In*EUROSAM '79, Lecture Notes in Computer Science*, volume 72, pages 216-225, 1979. MR**0575692 (81g:68061)**

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:
https://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.