Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



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 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.

References [Enhancements On Off] (What's this?)

Similar Articles

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

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
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.