<p>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:
<a href="http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html">http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html</a></p>

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

<p>This is the course's website:
<a href="http://stellar.mit.edu/S/course/6/fa10/6.895/">http://stellar.mit.edu/S/course/6/fa10/6.895/</a></p>

<p>Notes are available here:
<a href="http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/index.html">http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/index.html</a></p>

CC BY-SA 2.5
2010-11-07T16:42:38.793Z
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
CC BY-SA 3.0
2010-11-07T15:50:01.497Z
2011-06-16T17:17:46.740Z
2011-06-16T17:17:46.740Z
Dana Moshkovitz
<p>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, <a href="https://www.ams.org/journals/bull/2007-44-01/S0273-0979-06-01143-8/home.html"><em>On Dinur's Proof of the PCP Theorem</em></a>, Bull. Amer. Math. Soc. 44 (2007), 19-61 (<a href="http://people.csail.mit.edu/madhu/papers/jaikumar.pdf">preprint</a>).</p>

CC BY-SA 2.5
2010-08-17T00:16:19.480Z
2010-08-17T00:16:19.480Z
András Salamon
<p>I found the lecture notes from <a href="http://www.cs.washington.edu/education/courses/533/05au/">Guruswami &amp; O'Donnell course</a> (UW, 2005) very useful.</p>

CC BY-SA 2.5
2010-08-17T01:35:23.773Z
2010-08-17T01:35:23.773Z
Hung Q. Ngo
<p>For a VERY high level view I really liked Tim Gower's blog post from a few days ago:</p>

<p><a href="http://gowers.wordpress.com/2010/08/30/icm2010-avila-dinur-plenary-lectures/">http://gowers.wordpress.com/2010/08/30/icm2010-avila-dinur-plenary-lectures/</a></p>

<p>Really helped me "get" the connection to error correcting codes and to inapproximability.</p>

CC BY-SA 2.5
2010-09-04T14:21:18.353Z
2010-09-04T14:21:18.353Z
Mugizi Rwebangira
<p>There was a nice tutorial on the PCP theorem and applications a year ago. Their lecture notes should be helpful: <a href="http://arxiv.org/abs/1002.3864">Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)</a></p>

CC BY-SA 2.5
2010-08-17T04:12:15.567Z
2010-08-17T04:12:15.567Z
Robin Kothari
<p>For the original (and long) proof of the PCP theorem, I recommend Sudan's <a href="http://people.csail.mit.edu/madhu/pcp/course.html">notes</a> as a recap and Feige's <a href="http://www.wisdom.weizmann.ac.il/~feige/pcp.html">lecture notes</a> which explain the proof in detail.</p>

<p>Also, see <a href="http://blog.computationalcomplexity.org/2005/11/teaching-pcps.html">Fortnow's post</a> for other materials and useful discussions.</p>

CC BY-SA 2.5
2010-08-17T12:07:47.897Z
2010-08-17T13:34:26.200Z
2010-08-17T13:34:26.200Z
Zeyu
<p>There are 2 sources which seem particularly good to me. One, as someone above suggested is Venkat's and Ryan's lecture notes.</p>

<p>The other helpful source is <a href="http://www.cs.berkeley.edu/~luca/pcp/">these lecture notes</a> by Luca Trevisan.</p>

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

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

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

CC BY-SA 2.5
2010-09-09T01:36:22.210Z
2010-09-09T01:36:22.210Z
Akash Kumar
<p>I would suggest going through  Eli-Ben Sasson's <a href="http://www.cs.technion.ac.il/~eli/courses/PCP_Fall_2005/">lecture notes</a>. 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.</p>

CC BY-SA 2.5
2010-08-25T01:51:52.053Z
2010-08-25T01:51:52.053Z
Sarvagya Upadhyay
<p>My recommendation: </p>

<ul>
<li>for newbie computer scientists:</li>
</ul>

<p>1- <a href="http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/ICM.pdf" rel="nofollow">Probabilistically Checkable Proofs and Codes</a> by Irit Dinur</p>

<p>2- <a href="http://people.csail.mit.edu/madhu/papers/2009/pcpcacm.pdf" rel="nofollow">Probabilistically checkable proofs</a> by Madhu Sudan</p>

<p>3- Chapter 9 from <a href="http://rads.stackoverflow.com/amzn/click/052188473X" rel="nofollow">Goldreich book: Computational complexity, A conceptual perspective</a></p>

<ul>
<li>for professional computer scientists: </li>
</ul>

<p>1- <a href="http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf" rel="nofollow">The PCP Theorem by Gap Amplification</a> by Irit Dinur</p>

<p>2- <a href="http://people.csail.mit.edu/dmoshkov/courses/pcp/dinur_pcp_overview.pdf" rel="nofollow">On Dinur’s Proof of the PCP Theorem</a> by jaikumar Radhakrishnan and Madhu Sudan</p>

<p>3- Chapter 22 from <a href="http://rads.stackoverflow.com/amzn/click/0521424267" rel="nofollow">Arora and barak book: COMPUTATIONAL COMPLEXITY A Modern Approach</a></p>

<p>4- <a href="http://www.tcs.tifr.res.in/~prahladh/papers/thesis/phdthesis.ps" rel="nofollow">Robust PCPs of Proximity and Shorter PCPs</a> by Prahladh Harsha (that covers first proof of the PCP therorem)</p>

CC BY-SA 3.0
2011-03-20T16:21:45.653Z
2013-08-10T16:19:32.170Z
2013-08-10T16:19:32.170Z
j.s.
<p>For the "classical" (i.e., pre-Dinur) proof of the PCP theorem, I found Prahladh Harsha's thesis the best resource.</p>

CC BY-SA 2.5
2010-09-05T03:11:10.963Z
2010-09-05T03:11:10.963Z
user6584
<p>Both <a href="http://www.wisdom.weizmann.ac.il/~oded/cc-book.html">Goldreich's complexity textbook</a> and <a href="http://www.cs.princeton.edu/theory/complexity/">Arora and Barak's complexity textbook</a> have chapters devoted to explaining the proof of the PCP theorem (with pictures!).</p>

<p>Also, <a href="http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf">Dinur's paper</a> 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).</p>

CC BY-SA 4.0
2020-01-11T22:51:39.940Z
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
CC BY-SA 2.5
2010-08-17T00:17:09.027Z
I actually much prefer Dinur's paper to the discussion in Arora/Barak.
András Salamon
CC BY-SA 2.5
2010-08-16T21:55:05.167Z
2011-03-21T21:41:12.210Z
2011-03-21T21:41:12.210Z
Daniel Apon
<p>I'm familiar with a lot of results that use the <a href="https://en.wikipedia.org/wiki/PCP_theorem" rel="noreferrer">PCP theorem</a> (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))$). </p>

<p>What are good papers/books to read for that?</p>

<cc.complexity-theory><reference-request><pcp>
What are good references to understanding the proof of the PCP theorem?
Alexandre Passos
# What are good references to understanding the proof of the PCP theorem?

(Asked by: username_0 on 2010-08-16)

I'm familiar with a lot of results that use the [PCP theorem](https://en.wikipedia.org/wiki/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?

**Tags:** cc.complexity-theory, reference-request, pcp

---

## 11 answers

### Answer by username_2 on 2010-08-16. Score: 41 | Accepted answer

Both [Goldreich's complexity textbook](http://www.wisdom.weizmann.ac.il/~oded/cc-book.html) and [Arora and Barak's complexity textbook](http://www.cs.princeton.edu/theory/complexity/) have chapters devoted to explaining the proof of the PCP theorem (with pictures!).

Also, [Dinur's paper](http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf) 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).

> **Comments:**
> **username_3**: I actually much prefer Dinur's paper to the discussion in Arora/Barak.  
> **username_12**: 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?  

---

### Answer by username_1 on 2010-11-07. Score: 38

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>

> **Comments:**
> **username_2**: 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!  

---

### Answer by username_3 on 2010-08-17. Score: 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*](https://www.ams.org/journals/bull/2007-44-01/S0273-0979-06-01143-8/home.html), Bull. Amer. Math. Soc. 44 (2007), 19-61 ([preprint](http://people.csail.mit.edu/madhu/papers/jaikumar.pdf)).


---

### Answer by username_4 on 2010-08-17. Score: 21

I found the lecture notes from [Guruswami & O'Donnell course](http://www.cs.washington.edu/education/courses/533/05au/) (UW, 2005) very useful.


---

### Answer by username_5 on 2010-09-04. Score: 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.


---

### Answer by username_6 on 2010-08-17. Score: 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)](http://arxiv.org/abs/1002.3864)


---

### Answer by username_7 on 2010-08-17. Score: 13

For the original (and long) proof of the PCP theorem, I recommend Sudan's [notes](http://people.csail.mit.edu/madhu/pcp/course.html) as a recap and Feige's [lecture notes](http://www.wisdom.weizmann.ac.il/~feige/pcp.html) which explain the proof in detail.

Also, see [Fortnow's post](http://blog.computationalcomplexity.org/2005/11/teaching-pcps.html) for other materials and useful discussions.


---

### Answer by username_8 on 2010-09-09. Score: 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](http://www.cs.berkeley.edu/~luca/pcp/) 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)


---

### Answer by username_9 on 2010-08-25. Score: 12

I would suggest going through Eli-Ben Sasson's [lecture notes](http://www.cs.technion.ac.il/~eli/courses/PCP_Fall_2005/). 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.


---

### Answer by username_10 on 2011-03-20. Score: 11

My recommendation:

* for newbie computer scientists:

1- [Probabilistically Checkable Proofs and Codes](http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/ICM.pdf) by Irit Dinur

2- [Probabilistically checkable proofs](http://people.csail.mit.edu/madhu/papers/2009/pcpcacm.pdf) by Madhu Sudan

3- Chapter 9 from [Goldreich book: Computational complexity, A conceptual perspective](http://rads.stackoverflow.com/amzn/click/052188473X)

* for professional computer scientists:

1- [The PCP Theorem by Gap Amplification](http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf) by Irit Dinur

2- [On Dinur’s Proof of the PCP Theorem](http://people.csail.mit.edu/dmoshkov/courses/pcp/dinur_pcp_overview.pdf) by jaikumar Radhakrishnan and Madhu Sudan

3- Chapter 22 from [Arora and barak book: COMPUTATIONAL COMPLEXITY A Modern Approach](http://rads.stackoverflow.com/amzn/click/0521424267)

4- [Robust PCPs of Proximity and Shorter PCPs](http://www.tcs.tifr.res.in/~prahladh/papers/thesis/phdthesis.ps) by Prahladh Harsha (that covers first proof of the PCP therorem)


---

### Answer by username_11 on 2010-09-05. Score: 8

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


---

