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:
Contents:
Get all the notes together: As a pdf file, as a ps.gz file (0.5MB) or a ps file (2.3MB).
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).
(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).
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