65

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?

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
Alexandre Passos
  • 1,459
  • 12
  • 20

11 Answers11

41

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

Daniel Apon
  • 6,001
  • 1
  • 37
  • 53
  • 3
    I actually much prefer Dinur's paper to the discussion in Arora/Barak. – András Salamon Aug 17 '10 at 00:17
  • Would you mind if I asked how one gets that Max 3 Sat is not approximable using PCP? Because why would the PCP reduction for Max 3 Sat be Max 3 Sat? – Hao S Jan 11 '20 at 22:51
37

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

Dana Moshkovitz
  • 10,979
  • 1
  • 50
  • 77
  • 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 07 '10 at 16:42
23

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

András Salamon
  • 19,000
  • 3
  • 64
  • 150
21

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

Hung Q. Ngo
  • 311
  • 3
  • 7
20

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.

Mugizi Rwebangira
  • 1,278
  • 10
  • 18
17

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)

Robin Kothari
  • 13,617
  • 2
  • 60
  • 116
13

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.

Zeyu
  • 651
  • 8
  • 12
12

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)

Akash Kumar
  • 1,973
  • 16
  • 27
12

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.

Sarvagya Upadhyay
  • 121
  • 3
11

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)

j.s.
  • 705
  • 4
  • 11
8

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

user6584
  • 1,242
  • 7
  • 12