Seminar on Expanders

Instructor: Yan Ding  
Place: CoC 354
Time: Thursdays 4:30 to 6 pm.

Resources

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.

Last modified: Tue, Nov 15, 2005