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