CS369E: Expanders in Computer Science - Spring 2005
Expanders, constructions and their applications
- 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
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 ]
Note: Lecture on May 31 (Tuesday) in Gates 200
We will be adding more references as we go along. For the present, below are some sources of material on expanders:
- [Gur1] Lecture notes for a course on Codes and Pseudorandom objects given by Venkatesan Guruswami at the University of Washington, Seattle.
- [LW] Lecture notes for a course on expanders given by Nati Linial and Avi Wigderson at the Hebrew University, Israel.
- [Vad] Lecture notes for a course on pseudorandomness given by Salil Vadhan at Harvard. (Lectures 8, 9, 10 and 11 deal with expanders)
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).
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.