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.
Exercises: [ex1 (due Nov 16)]
Take the survey about the exercise
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.
- 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
- Book on spectral and algebraic graph theory by Dan Spielman