65
$\begingroup$

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?

Improve this question
$\endgroup$
0

11 Answers 11

Reset to default
41
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ I actually much prefer Dinur's paper to the discussion in Arora/Barak. $\endgroup$
    – András Salamon
    Commented Aug 17, 2010 at 0:17
  • $\begingroup$ 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? $\endgroup$
    – Hao S
    Commented Jan 11, 2020 at 22:51
38
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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! $\endgroup$
    – Daniel Apon
    Commented Nov 7, 2010 at 16:42
23
$\begingroup$

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

Improve this answer
$\endgroup$
21
$\begingroup$

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

Improve this answer
$\endgroup$
20
$\begingroup$

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.

Improve this answer
$\endgroup$
17
$\begingroup$

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)

Improve this answer
$\endgroup$
13
$\begingroup$

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.

Improve this answer
$\endgroup$
12
$\begingroup$

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.

Improve this answer
$\endgroup$
12
$\begingroup$

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)

Improve this answer
$\endgroup$
11
$\begingroup$

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)

Improve this answer
$\endgroup$
8
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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