I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1))$).

What are good papers/books to read for that?

  • Should this be a community wiki? – Matthias Aug 16 '10 at 21:50
  • Not necessary I think. It's a very specific question that will have specific answers. – Suresh Venkat Aug 16 '10 at 21:55

11 Answers 11

up vote 38 down vote accepted

Both Goldreich's complexity textbook and Arora and Barak's complexity textbook have chapters devoted to explaining the proof of the PCP theorem (with pictures!).

Also, Dinur's paper is worthwhile to read, if you haven't tried to tackle it yet. It's at least more approachable (in my opinion) than the original proof, and you can get a good intuition for how the proof works by skimming just the first 12 pages (and delve into the technical proofs contained in the latter chunk of the paper later, if you prefer).

  • 3
    I actually much prefer Dinur's paper to the discussion in Arora/Barak. – András Salamon Aug 17 '10 at 0:17
  • Just a note that the link to Dinur's paper was taken down. I have a local copy but I'm not sure I should host it myself (out of respect - I figure it was taken down for a reason). – Ross Snider Mar 20 '11 at 16:58
  • 2
    well, Dinur's at Weizmann, and the link above was to her old site at Hebrew University. Here's the current link: wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf – Cong Han Mar 21 '11 at 5:39

In 2008 Irit Dinur and I taught a course on PCP at Weizmann, including both the algebraic and the combinatorial proofs. Hand-written lecture notes are available for most classes: http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html

This semester I'm teaching a PCP course at MIT that contains the material of the old course, more comprehensive treatment of parallel repetition and the unique games conjecture, as well as recent results (from 2008-2009), like low error composition and optimality of Semidefinite Programming for constraint satisfaction problems assuming the Unique Games Conjecture. I also dedicate time to teaching error correcting codes, expanders, information theory and Fourier analysis.

This is the course's website: http://stellar.mit.edu/S/course/6/fa10/6.895/

Notes are available here: http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/index.html

  • 1
    Cool, those are some excellent notes. I'm actually happy to finally see an author attached to "An Illustrated History of the PCP Theorem." I've seen it multiple places before, but never with a source cited! – Daniel Apon Nov 7 '10 at 16:42

Dinur's paper (linked in the answer by Daniel Apon) is well written and worth reading. An extended discussion was also published about this paper and the proof, which is useful when reading the paper itself: Jaikumar Radhakrishnan and Madhu Sudan, On Dinur's Proof of the PCP Theorem, Bull. Amer. Math. Soc. 44 (2007), 19-61 (preprint).

I found the lecture notes from Guruswami & O'Donnell course (UW, 2005) very useful.

For a VERY high level view I really liked Tim Gower's blog post from a few days ago:

http://gowers.wordpress.com/2010/08/30/icm2010-avila-dinur-plenary-lectures/

Really helped me "get" the connection to error correcting codes and to inapproximability.

There was a nice tutorial on the PCP theorem and applications a year ago. Their lecture notes should be helpful: Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

For the original (and long) proof of the PCP theorem, I recommend Sudan's notes as a recap and Feige's lecture notes which explain the proof in detail.

Also, see Fortnow's post for other materials and useful discussions.

I would suggest going through Eli-Ben Sasson's lecture notes. Also, Prahladh Harsha's lecture notes contain and exposition of both the proofs of PCP Theorem. The link to Prahladh's course can be found on his TIFR webpage (U Chicago Fall 2007). The course notes of Venkat Guruswami and Ryan O'Donnell (as suggested by Hung Q. Ngo) are very good too.

There are 2 sources which seem particularly good to me. One, as someone above suggested is Venkat's and Ryan's lecture notes.

The other helpful source is these lecture notes by Luca Trevisan.

Currently, this course is being offered at Georgia Tech by Prasad Raghvendra. Sadly the page is not up yet.

This brings me to another source by Subhash Khot. Search for it on Google. You should be able to find those.

(Personally, I have not looked up Khot's notes either, but just remembered that he taught this course once at GaTech as well)

My recommendation:

  • for newbie computer scientists:

1- Probabilistically Checkable Proofs and Codes by Irit Dinur

2- Probabilistically checkable proofs by Madhu Sudan

3- Chapter 9 from Goldreich book: Computational complexity, A conceptual perspective

  • for professional computer scientists:

1- The PCP Theorem by Gap Amplification by Irit Dinur

2- On Dinur’s Proof of the PCP Theorem by jaikumar Radhakrishnan and Madhu Sudan

3- Chapter 22 from Arora and barak book: COMPUTATIONAL COMPLEXITY A Modern Approach

4- Robust PCPs of Proximity and Shorter PCPs by Prahladh Harsha (that covers first proof of the PCP therorem)

For the "classical" (i.e., pre-Dinur) proof of the PCP theorem, I found Prahladh Harsha's thesis the best resource.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.