Skip to Main Content

Bulletin of the American Mathematical Society

The Bulletin publishes expository articles on contemporary mathematical research, written in a way that gives insight to mathematicians who may not be experts in the particular topic. The Bulletin also publishes reviews of selected books in mathematics and short articles in the Mathematical Perspectives section, both by invitation only.

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

The 2020 MCQ for Bulletin of the American Mathematical Society is 0.84.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


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


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.
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
  • Email:
  • 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:
  • MathSciNet review: 2265009