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