Feb 13, 2010

CS369E: Expanders in Computer Science

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

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:
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.



No comments:

Post a Comment

Subscribe to: Post Comments (Atom)