CS369E: Expanders in Computer Science - Spring 2005
Expanders, constructions and their applications
Time: Mon 2:15-4:05pm
Location: Educ 130 (Stanford)
microsoft DOT com) and
(<firstname> AT tti-c DOT org)
Complete Lectures Notes (82 pages)
| gzipped-pdf ]
Individual Lectures (below)
- Lecture 1 (Apr 4): Introduction, motivation and some
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)
[Alo, BL, Fri].
Lecture Notes (by Geir Helleloid): [ ps |
- 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 |
- Lecture 4 (Apr 25): Derandomization
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
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
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
Ref: [Gur2, GI, RVW, SS, Zem]
- Lecture 7 (May 16): Zig-Zag Product and Undirected Connectivity
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 ]
- Lecture 8 (May 31): The
Dinur's Proof of The PCP Theorem
Lecture Notes (by Krishnaram Kenthapadi): [ ps | pdf ]
Note: Lecture on May 31 (Tuesday) in Gates 200
Style files for scribes: sample.tex
and preamble.tex .
We will be adding more references as we go along. For the present,
below are some sources of material on 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
[AKS] Miklos Ajtai, Janos Komlos, Endre Szemeredi:
"Deterministic Simulation in LOGSPACE", STOC 1987: 132-140.
[Alo] Noga Alon, "Eigenvalues and expanders", Combinatorica 6(2):
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
[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,
[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).
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
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.
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
(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
[Zem] Gilles Zemor: "On Expander
Codes", IEEE Transactions on Information Theory 47(2):835-837
Students taking the course for credit will be expected to:
- Attend lectures
- Scribe notes for a lecture or two (rare) in
to Cynthia and/or Prahladh (not necessarily in class) the proofs of
some of the theorems presented without proof in lecture.
This page has been accessed at least
times since May 15, 2005.