Related classes and notes
| Sep 8 2005 | Nikhil | Definitions and existence of expanders; connection to eigenvalue gap; expander mixing lemma; expanders as integrality gap examples. |
| Sep 15, 2005 | Tejas | Random Walks on expanders; application to amplification of success probability in randomized algorithms. |
| Sep 22, 2005 | Parikshit | Expander based construction of Error correcting codes |
| Sep 29, 2005 | -- | No meeting due to Subhash's talk |
| Oct 6, 2005 | Milena | Application to computer networks |
| Oct 13, 2005 | Yan | The Impagliazzo-Nisan-Wigderson pseudorandom generator for two-party communication protocols and space-bounded computations. |
| Nov 4, 2005 | Yan | Explicit Construction of expanders: Zig-Zag Product |
| Nov 10, 2005 | David | s-t connectivity in Log space. (Reingold's result) |
| Nov 17, 2005 | Deeparnab | Trevisan's Algorithm for Unique games. |
| Nov 29, 2005 | Farbod | Reingold, Trevisan and Vadhan's follow up work on Reingold's result: Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem |
| Dec 1, 2005 | Subrahmanyam | Semi-direct Products in Groups and Zig-Zag products in graphs: Connections and Applications. Noga Alon, Alexander Lubotsky, Avi Wigderson. |
| Dec 8, 2005 | Yan | Dinur's proof of PCP theorem. |