Expander Graphs and their applications - Fall 2020 course
Time: Monday+Tuesday 9:30 - 11:00
Start date: Monday, November 2, 2020
This is a basic introductory course to expander graphs.
Expanders are fundamental objects with many applications in computer science and beyond.
We will learn about basic properties of expander graphs and some of the most fascinating applications such as
towards constructing error correcting codes, derandomization, networks, approximate counting, and more.
The final grade will be based on exercises, class participation and a project presentation.
List of projects: [here]. Please also signup in the same googledoc for a prelim meeting with me regarding the project (Feb 22/23).
Presentations will take place on March 1 & 2.
Exercises: [ex1] [ex2] [ex3]
Lectures by weeks:
Introduction and three applications of expander graphs. Based on chapter 1 in HLW.
- [Video L03]
Combinatorial expansion, and spectral / algebraic expansion. The expander mixing lemma (EML). Partly based on chapter 2 in HLW.
- [Worksheet L05] ("inverse classroom" - worked on problems in groups, here are solutions by "Group 1")
- [Video L06]
Spectral theorem, the Laplacian of a graph, Cheeger's inequality connecting edge expansion and spectral gap.
- [Worksheet L08] More random walks, weighted graphs, graph products
- [Video L09]
Margulis-Gabber-Galil explicit construction of expanders. See also lecture video by James Lee, and notes by Luca Trevisan.
- [Video L11]
Zigzag construction of expanders. See also lecture notes by Yotam Dikstein.
Cayley graphs of Abelian groups, their eigenvectors, and the Fourier transform. See also these notes.
- [Video L13] [notes 13]
Cayley graphs of Abelian groups, their eigenvectors, and the Fourier basis. The cycle graph and the Hamming cube.
[Video L14] [notes 14]
Expander codes, see also these notes by Venkatesan Guruswami.
- [Video L15] [notes 15]
Error correcting codes from spectral expanders, and Zemor's decoding algorithm.
[Video L16] [notes 16]
Distance amplification, parity along paths, and epsilon-biased sets. See this paper by Amnon Ta-Shma.
- [Video L17]
[Video L18][notes 17-18]
Constraint satisfaction problems, algorithms when the underlying graph is related to an expander.
- [Video L19]
Cheeger's inequality and sparsest cut.
Leighton-Rao linear-programming relaxation for sparsest cut.
- [Video L21] [notes 21-22]
Markov chains, convergence of walks on exponential-sized configuration graphs, high dimensional expanders.
Random-walk expansion and link expansion.
- [Video L23] [notes 23]
End high dimensional expanders.
- [Video L24]
Some open questions in expanders. See also this [lecture] by Avi Wigderson.
- Survey on "EXPANDER GRAPHS AND THEIR APPLICATIONS" by Hoory Linial and Wigderson [HLW]
- Lecture notes from a course by Linial and Wigderson with the same title
- Lecture notes on expansion and spectral graph theory by Luca Trevisan (also an earlier version)
- Book on spectral and algebraic graph theory by Dan Spielman