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