CS369E: Expanders in Computer Science - Spring 2005

Expanders, constructions and their applications

Time: Mon 2:15-4:05pm
Location: Educ 130 (Stanford)
Instructors : (dwork AT microsoft DOT com) and (<firstname> AT tti-c DOT org)
Homepage: http://cs369e.stanford.edu

Course Announcement

Lectures

Complete Lectures Notes (82 pages) [ ps | gzipped-ps | pdf | gzipped-pdf ]
Individual Lectures (below)

1. 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 ]
   
   
2. 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 ]
   
   
3. 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 ]
   
   
4. 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 ]
   
   
5. 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]
   
   
6. 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]
   
   
7. 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]
   
   
8. 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:

• [Gur1] Lecture notes for a course on Codes and Pseudorandom objects given by Venkatesan Guruswami at the University of Washington, Seattle.
  http://www.cs.washington.edu/education/courses/590vg/03wi/notes.html
• [LW] Lecture notes for a course on expanders given by Nati Linial and Avi Wigderson at the Hebrew University, Israel.
  http://www.math.ias.edu/~boaz/ExpanderCourse/
• [Vad] Lecture notes for a course on pseudorandomness given by Salil Vadhan at Harvard. (Lectures 8, 9, 10 and 11 deal with expanders)
  http://www.courses.fas.harvard.edu/~cs225/Lectures/

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.

1. [AKS] Miklos Ajtai, Janos Komlos, Endre Szemeredi: "Deterministic Simulation in LOGSPACE", STOC 1987: 132-140.
2. [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.
3. [BL] Yonatan Bilu, and Nati Linial, "Lifts, discrepancy and nearly optimal spectral gaps", To appear in Combinatorica, (A preliminary version appeared in FOCS 2004).
4. [Din] Irit Dinur, "The PCP Theorem by Gap Amplification", ECCC Technical Report TR05-046, 2005.
5. [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).
6. [Gur2] Venkatesan Guruswami. Error-correcting codes and Expander graphs SIGACT News, 35(3): 25-41, September 2004.
7. [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).
8. [INW] Russell Impagliazzo, Noam Nisan, Avi Wigderson: "Pseudorandomness for network algorithms", STOC 1994: 356-364
9. [IZ] Russell Impagliazzo, David Zuckerman: "How to Recycle Random Bits", FOCS 1989: 248-253.
10. [Lov] Lazlo Lovasz: ``Random Walks on Graphs: A Survey'', Combinatorics, Paul Erdos is Eighty, Vol. 2, Janos Bolyai Mathematical Society, Budapest, 1996, 353--398
11. [Lin] Nati Linial, "Expanders, eigenvalues and all that", Invited Talk, NIPS, Dec 2004.
    (A nice introduction to expanders).
12. [Nis] Noam Nisan: "Pseudorandom generators for space-bounded computation", Combinatorica 12(4): 449-461 (1992).
13. [Rei] Omer Reingold: "Undirected ST-Connectivity in Logspace", ECCC Tech Report TR04-094, 2004.
14. [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.
15. [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)
16. [SW] Amir Shpilka, Avi Wigderson: "Derandomizing homomorphism testing in general groups". STOC 2004: 427-435
17. [SS] Michael Sipser, Daniel A. Spielman: Expander codes. IEEE Transactions on Information Theory 42(6): 1710-1722 (1996)
18. [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.

This page has been accessed at least times since May 15, 2005.

Prahladh Harsha