Course 67659: Expander graphs and their applications

Nati Linial and Avi Wigderson

Class Hours: Monday 12-2, Sprinzak 115

Avi's Office hours: Wednesday 9-10:30, Ross 215

Course Requirements: 50% - lecture notes , 50% - exercises

TA / Lecture notes coordinator: Shlomoh Hoory (shlomoh@cs.huji.ac.il).

Bulletin Board:

  • The lecture notes are on-line.

  • Contents:

  • Lecture Notes

  • Course Plan

  • Exercises

  • References

  • Lecture Notes

    Get all the notes together: As a pdf file, as a ps.gz file (0.5MB) or a ps file (2.3MB).

  • Lecture 1 (ps file) - The Magical Mystery Tour / Ran Gilad-Bachrach
  • Lecture 2 (ps file) - Graph Expansion & Eigenvalues / Danny Harnik
  • Lecture 3 (ps file) - Random Walks on Expander Graphs / Boaz Barak and Udi Wieder
  • Lecture 4 (ps file) - a Geometric View of Expander Graphs / Eran Ofek and Erez Waisbard
  • Lecture 5 (ps file) - Expander graphs have a large spectral gap / Yael Vinner
  • Lecture 6 (ps file) - Upper Bound on Spectral Gap / Yishai Beeri
  • Lecture 7 (ps file) - The Margulis construction / Statter Dudu
  • Lecture 8 (ps file) - The Zig Zag Product / Eyal Bigman
  • Lecture 9 (ps file) - Metric Embedding / Tamir Hazan
  • Lecture 10 (ps file) - Error Correcting Codes / Elon Portugaly
  • Lecture 11 (ps file) - Lossless Conductors and Expanders / Ariel Elbaz, Yuval Filmus and Michal Igell
  • Lecture 12 (ps file) - Cayley graph expanders / Eyal Rozenman
  • Lecture 13 (ps file) - On eigenvalues of random graphs and the abundance of Ramanujan graphs / Danny Gutfreund
  • Lecture 14 (ps file) - Some Eigenvalue Theorems / Yonatan Bilu
  • Get a .zip file of all individual .ps files: notes.zip

    The notes were written using LaTeX, borrowing from a template of Oded Goldreich. Instructions for writing notes (ps file). A template for writing notes (.tex file).


    Course Plan

    (A first approximation of the topics to be covered, not completely in order)

    Lecture 1 - Introduction, History and Motivation: Superconcentrators for lower bounds (Valiant). Probabilistic existence of expanders (Pinsker). Explicit constructions (Margulis) (from Property T). Amplification without extra bits (Karp, Pippenger and Sipser).
    Scribe:??

    Algebraic graph theory: Spectrum of the adjencancy matrix. 2nd eigen-value. Trace and Girth (Alon- Boppana). Links: Noga Alon

    Notions of expansion: Vertex expansion, Edge expansion, Conductance, 2nd e-value, last e-value, connections to isoperimetric inequalities, Alon's theorem (and comparison with Jerrum-Sinclair)

    Properties of expanders: Independent set, Chromatic number, diameter, mixing time, small sets are sparser, expander mixing lemma, expansion by d/2. Kahale's theorem of tightness. Girth (later for LPS).

    Continuous connections: Manifolds, Laplacian, Cheeger - how to build manifolds from sequences of graphs and vice versa (maintaining e-value bounds). Hyperbolic manifolds? The upper half plane. Approx manifolds by the graph on fundamental domains and group action.

    Abelian Groups and Cayley graphs: Fourier transform on Abelian groups. Cayley graphs of Abelian groups - computing the eigen values from the Fourier coefficients. Limits on expansion of Abelian groups. Connection to Linear codes and epsilon biased sets (Alon - Roichman).

    ``Abelian'' consturctions: Gaber-Galil, discrete Fourier proof by Jimbo-Marouka (simplified by Boppana). Symmetrization conjecture (Linial)

    Non-Abelian groups and Cayley graphs: Basic representation theory. Property T and its connection to eigen-values. Margulis Theorem - expansion in SL_n(p), n>2. Graphs of groups acting on sets. Property Tau and its connection to eigen-values. Selberg's theorem and Expansion in SL_2(p). Expansion for all gen sets of SL_2(Z) - is expansion a property of the group? (Lubotzky-Weiss). Elementary proof of Selberg (Sarnak-Xu).

    LPS,Margulis Ramanujan graph construction.

    Zig-Zag theorem & elementary construction: Expanders as entropy waves. Linear algebra proof. Elementary construction. Achieving lambda d^{3/4} (and perhaps improvement to d^{2/3}) (still far from Ramanujan).

    Zig-Zag and Semi-direct product: iterative const of Cayley expanders (Alon-Lubotzky-Wigderson , Meshulam-Wigderson).

    Applications - Error correcting codes: Introduction to Error Correcting Codes. Erasure codes. Shanon's Theorems. Gilbert Varshamov bound. Statement of MRRW. Capacity achieving codes for erasures from expanders (Alon-Luby). Gallager, Tanner, Sipser-Speilman,... ECC from (lossless) expanders

    Min-entropy zigzag and lossless expanders: (Capalbo-Reingold-Vadhan-Wigderson)

    Applications - finding disjoint paths in expanders: Peleg-Upfal, Arora-Leighton-Maggs, Frieze-??(FOCS'01). Links: David Peleg Sanjeev Arora

    Applications - derandomization: Expander walks (Ajtai-Komlos-Szemeredi, Cohen-Wigderson, Impagliazzo-Zuckerman). Weak sources and Extractors Links: David Zuckerman

    Applications - small space derandomization: Expanders as discrepancy sets for rectangles (and low communication comp protocols). Impagliazzo-Nisan-Wigderson version of Nisan's generator. Links: Russell Impagliazzo Noam Nisan

    Combinatorial applications: Universal graphs for all const deg trees (Friedman-Pippenger). Limits on embeddings (+ semi-definite programming representation of L2 embeddings and connections to e-value) (Linial-London-Rabinovich). ...

    Applications - data structures: Distributed memories (Upfal-Wigderson). One bit membership queries (Miltersen et al).


    Exercises

  • Exercise 1 - due April 8th 2002. (LaTeX file).
  • Exercise 2 - due April 8th 2002 (with Exercise 1). (LaTeX file).
  • Exercise 3 - due April 15th 2002. (LaTeX file)
  • Exercise 4 - due April 22th 2002. (LaTeX file)
  • Exercise 5 - due April 29th 2002. (LaTeX file)
  • Exercise 6 - due May 6th 2002. (LaTeX file)
  • Exercise 7 - due May 13th 2002. (LaTeX file)
  • Exercise 8 - due June 10th 2002. (LaTeX file)
  • Exercise 9 - due June 10th 2002. (LaTeX file)

  • References

    A list of references is available as a .bib file.

    Book: G. Davidoff, P. Sarnak, A. Vallete Elementary Number Theory, Group Theory and Ramanujan Graphs. [ pdf file (1MB) ps file (1.7MB) ]


    Page maintained by Boaz Barak