This course is taken by Manindra Agrawal. Half way down the course, he started on the PCP theorems and I thought it would be good to scribe the notes. I shall try to make it as detailed as possible.
Goes without saying, if anyone notices any serious mistakes in my notes, please tell me.
Goes without saying, if anyone notices any serious mistakes in my notes, please tell me.
| Lecture 1 | : | Derandomization: The Deathly Hallows | [PDF] | [TeX] |
| Lecture 2 | : | Expanders: Spectral and Vertex Expansion | [PDF] | [TeX] |
| Lecture 3 | : | Random Walks on Expanders | [PDF] | [TeX] |
| Lecture 4 | : | Constructing Expanders: The Zig-Zag Product | [PDF] | [TeX] |
| Lecture 5 | : | Towards the Proof of PCP Theorem | [PDF] | [TeX] |
| Lecture 6 | : | Gap Amplification | [PDF] | [TeX] |
And a single file with all the above lectures together: here.
