Authors View :
This is a course I have taken at IITK. It is offered by Manindra Agrawal. I decided to scribe the notes of the PCP theorems, extractors, expanders etc. Though these were covered in the course by Arvind (complexity 2), it is useful to have another perspective as well.
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: Click here.
No comments:
Post a Comment