http://ttic.uchicago.edu/~prahladh/teaching/spring05/index.html CS369E: Expanders in Computer Science - Spring 2005
Expanders, constructions and their applications
Time: Mon 2:15-4:05pm
Location: Educ 130 (Stanford)
Instructors : Cynthia Dwork (dwork AT microsoft DOT com) and Prahladh Harsha (<firstname> AT tti-c DOT org)
Homepage: http://cs369e.stanford.edu
Lectures
Complete Lectures Notes (82 pages) [ ps | gzipped-ps | pdf | gzipped-pdf ]
Individual Lectures (below)
- Lecture 1 (Apr 4): Introduction, motivation and some applications
Definition; applications: time-space tradeoffs (super-concentrators), (almost everywhere) Byzantive agreement, Amplification with no extra random bits (Karp Pippenger Sipser), Expander Codes, use of expanders in metric embeddings
Ref: [Lin, Rob].
Lecture Notes (by Arpita Ghosh): [ ps | pdf ]
- Lecture 2 (Apr 11): Expanders and eigen-values
Probabilistic method - existence of expanders (Pinsker);
eigen-value connection, spectral gap implies expansion, expander mixing lemma, expanders have large spectral gap (Alon), Statements w/o proof: Alon's 2nd eigen-value conjecture (Friedman), Ramanujan graphs, converse to expander mixing lemma (Bilu and Linial)
Ref: [Alo, BL, Fri].
Lecture Notes (by Geir Helleloid): [ ps | pdf ]
- Lecture 3 (Apr 18): Random Walks
Random walks in (general) undirected graphs, undirected connectivity is in randomized logspace (Aleliunas et. al.); Universal Traversal Sequences (UTS) - definition and existence; Random walks on expanders
Ref: [Lov]
Lecture Notes (by David Arthur): [ ps | pdf ]
- Lecture 4 (Apr 25): Derandomization
Pseudo-random generators: AKS generator, INW construction of Nisan's Generator.
Ref: [AKS, INW, IZ, Nis]
Lecture Notes (by Adam Barth and Prahladh Harsha): [ ps | pdf ]
- Lecture 5 (May 2): Derandomized Linearity Testing & Error Correcting Codes
Part 1: Derandomized Linearity Testing (Shpilka-Wigderson); Lecture Notes (by Adam Barth): [ ps | pdf ]
Part 2: Introduction to Error-Correcting Codes and basic construction of linear decodable codes (Sipser-Spielman, Zemor)
Ref: [Gur2, SW, SS, Zem]
- Lecture 6 (May 9): Error Correcting Codes and Expander Constructions
Part 1: Linear time decodable codes (Sipser-Spielman, Guruswami-Indyk, Zemor); Lecture Notes (by Hovav Shacham): [ ps | pdf ]
Part 2: Explicit Construction of Expanders: Margulis, Gaber-Galil, LPS (all without proof); Zig-Zag expanders (Reingold-Vadhan-Wigderson)
Ref: [Gur2, GI, RVW, SS, Zem]
- Lecture 7 (May 16): Zig-Zag Product and Undirected Connectivity in Logspace
Part 1: Zig-Zag Product and Expander Construction (Reingold-Vadhan-Wigderson); Lecture Notes (by Geir Helleloid): [ ps | pdf ]
Part 2: Reingold's proof of SL=L; Lecture Notes (by Cynthia Dwork and Prahladh Harsha): [ ps | pdf ]
Ref: [RVW, Rei]
- Lecture 8 (May 31): The PCP Theorem
Dinur's Proof of The PCP Theorem
Lecture Notes (by Krishnaram Kenthapadi): [ ps | pdf ]
Ref: [Din]
Note: Lecture on May 31 (Tuesday) in Gates 200
Style files for scribes: sample.tex and preamble.tex .
References
We will be adding more references as we go along. For the present, below are some sources of material on expanders:
Main references:
Other References:
The links below point to the actual location of papers at the author's homepages or other electronic repositories and the papers are not reposted locally.
- [AKS] Miklos Ajtai, Janos Komlos, Endre Szemeredi: "Deterministic Simulation in LOGSPACE", STOC 1987: 132-140.
- [Alo] Noga Alon, "Eigenvalues and expanders", Combinatorica 6(2): 83-96 (1986).
A writeup of the proof that "expansion implies spectral gap" from Alon's paper can be found in pages 14-16 of the following thesis:
David Xiao, "The Evolution of Expander Graphs", AB Thesis, Harvard University, 2003. - [BL] Yonatan Bilu, and Nati Linial, "Lifts, discrepancy and nearly optimal spectral gaps", To appear in Combinatorica, (A preliminary version appeared in FOCS 2004).
- [Din] Irit Dinur, "The PCP Theorem by Gap Amplification", ECCC Technical Report TR05-046, 2005.
- [Fri] Joel Friedman, "A proof of Alon's second eigenvalue conjecture and related problems", CoRR cs.DM/0405020: (2004) (A preliminary version appeared in STOC 2003).
- [Gur2] Venkatesan Guruswami. Error-correcting codes and Expander graphs SIGACT News, 35(3): 25-41, September 2004.
- [GI] Venkatesan Guruswami, Piotr Indyk: "Linear time encodable/decodable codes with near-optimal rate", To appear in IEEE Transactions on Information Theory. (Preliminary Version in STOC'02).
- [INW] Russell Impagliazzo, Noam Nisan, Avi Wigderson: "Pseudorandomness for network algorithms", STOC 1994: 356-364
- [IZ] Russell Impagliazzo, David Zuckerman: "How to Recycle Random Bits", FOCS 1989: 248-253.
- [Lov] Lazlo Lovasz: ``Random Walks on Graphs: A Survey'', Combinatorics, Paul Erdos is Eighty, Vol. 2, Janos Bolyai Mathematical Society, Budapest, 1996, 353--398
- [Lin] Nati Linial, "Expanders, eigenvalues and all that", Invited Talk, NIPS, Dec 2004.
(A nice introduction to expanders). - [Nis] Noam Nisan: "Pseudorandom generators for space-bounded computation", Combinatorica 12(4): 449-461 (1992).
- [Rei] Omer Reingold: "Undirected ST-Connectivity in Logspace", ECCC Tech Report TR04-094, 2004.
- [RVW] Omer Reingold, Salil Vadhan, and Avi Wigderson: "Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors", Annals of Math `02.
- [Rob] Sara Robinson, "Computer Scientist Finds Small-Memory Algorithm for Fundamental Graph Problem", SIAM News, Volume 38, Number 1, January/February 2005.
(A news report on Reingold's result, also covers some history on expanders) - [SW] Amir Shpilka, Avi Wigderson: "Derandomizing homomorphism testing in general groups". STOC 2004: 427-435
- [SS] Michael Sipser, Daniel A. Spielman: Expander codes. IEEE Transactions on Information Theory 42(6): 1710-1722 (1996)
- [Zem] Gilles Zemor: "On Expander Codes", IEEE Transactions on Information Theory 47(2):835-837 (2001).
Requirements
Students taking the course for credit will be expected to:
- Attend lectures
- Scribe notes for a lecture or two (rare) in LATEX.
- Present to Cynthia and/or Prahladh (not necessarily in class) the proofs of some of the theorems presented without proof in lecture.