CS369E: Expanders in Computer Science  Spring 2005
Expanders, constructions and their applications
Time: Mon 2:154:05pm
Location: Educ 130 (Stanford)
Instructors :
(dwork AT
microsoft DOT com) and
(<firstname> AT ttic DOT org)
Homepage: http://cs369e.stanford.edu
Lectures
Complete Lectures Notes (82 pages)
[ ps
 gzippedps
 pdf
 gzippedpdf ]
Individual Lectures (below)
 Lecture 1 (Apr 4): Introduction, motivation and some
applications
Definition; applications: timespace tradeoffs
(superconcentrators), (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 eigenvalues
Probabilistic method  existence of expanders (Pinsker);
eigenvalue connection, spectral gap implies expansion, expander mixing lemma,
expanders have large spectral gap (Alon), Statements w/o proof: Alon's 2nd
eigenvalue 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
Pseudorandom
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
(ShpilkaWigderson); Lecture Notes (by Adam Barth): [ ps  pdf ]
Part 2: Introduction to ErrorCorrecting Codes and basic construction
of linear decodable codes (SipserSpielman, Zemor)
Ref: [Gur2, SW, SS, Zem]
 Lecture 6 (May 9): Error Correcting Codes and Expander
Constructions
Part 1: Linear time decodable codes (SipserSpielman, GuruswamiIndyk,
Zemor); Lecture Notes (by Hovav Shacham): [ ps  pdf ]
Part 2: Explicit Construction of Expanders: Margulis, GaberGalil, LPS (all without proof); ZigZag expanders
(ReingoldVadhanWigderson)
Ref: [Gur2, GI, RVW, SS, Zem]
 Lecture 7 (May 16): ZigZag Product and Undirected Connectivity
in Logspace
Part 1: ZigZag Product and Expander Construction
(ReingoldVadhanWigderson); 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: 132140.

[Alo] Noga Alon, "Eigenvalues and expanders", Combinatorica 6(2):
8396 (1986).
A writeup of the proof that "expansion implies spectral gap" from Alon's
paper can be found in pages 1416 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 TR05046,
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.
Errorcorrecting codes and Expander graphs
SIGACT News, 35(3): 2541, September 2004.

[GI] Venkatesan Guruswami, Piotr Indyk: "Linear
time encodable/decodable codes with nearoptimal 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: 356364

[IZ] Russell Impagliazzo, David Zuckerman: "How to
Recycle Random Bits", FOCS 1989: 248253.

[Lov] Lazlo Lovasz: ``Random Walks on Graphs: A
Survey'', Combinatorics, Paul Erdos is Eighty, Vol. 2, Janos
Bolyai Mathematical Society, Budapest, 1996, 353398

[Lin] Nati Linial, "Expanders,
eigenvalues and all that", Invited Talk, NIPS, Dec 2004.
(A nice
introduction to expanders).

[Nis] Noam Nisan: "Pseudorandom generators for spacebounded
computation", Combinatorica 12(4): 449461 (1992).

[Rei] Omer Reingold: "Undirected
STConnectivity in Logspace", ECCC Tech Report TR04094, 2004.

[RVW] Omer Reingold, Salil Vadhan, and Avi Wigderson: "Entropy
Waves, The ZigZag Graph Product, and New ConstantDegree Expanders
and Extractors", Annals of Math `02.

[Rob] Sara Robinson, "Computer
Scientist Finds SmallMemory 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: 427435

[SS] Michael Sipser, Daniel A. Spielman: Expander
codes. IEEE Transactions on Information Theory 42(6): 17101722
(1996)

[Zem] Gilles Zemor: "On Expander
Codes", IEEE Transactions on Information Theory 47(2):835837
(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.
This page has been accessed at least
times since May 15, 2005.