Expander graphs have been extensively studied in mathematics over the past several decades, and in that time found numerous applications to computer science, such as in the design of fast error correcting codes and resilient networks. High-dimensional expanders is an emergent area that ties together topology, algebra, and combinatorics, and underlies a surprising range of applications in computer science, ranging from fast MCMC sampling to efficient quantum codes.
The first half of this course will cover classical topics in expander graphs, the second half recent topics in high-dimensional expanders.
- Lectures: Tuesdays / Thursdays 11-12:20
- Office hours: Shachar - Fridays 10-11am; Max - Tuesday 12:30-1:30
Due to COVID, all meetings (lectures, office hours) will be remote on zoom.
Evaluation
Evaluation will be based on homeworks and a final project. Both can be solved individually or in pairs.
Tentative schedule:
- Part I: Expander graphs
- Week 1 - Introduction to expanders: combinatorial expansions, spectral expansion, Cheeger inequality, expander mixing lemma
- Week 2 - Random walks on expanders: spectral analysis, convergence rate, hitting probability, application to error reduction in randomized algorithms
- Week 3 - Applications of expanders in CS: arithmetic circuits for linear algebra, error correcting codes
- Week 4 - Optimal expanders: Ramanujan graphs, infinite trees, Alon-Boppana
- Week 5 - Constructions of expanders: Algebraic constructions (Margulis-Gaber-Galil), Combinatorial constructions (Zig-zag)
- Part II: High-Dimensional Expanders (HDX)
- Week 6 - Introduction to HDX: simplicial complexes, local-spectral expanders, trickle down lemma, basic constructions
- Week 7 - Random walks on HDX: averaging operators, upper and lower walks, random-walk HDX, different decompositions
- Week 8 - Sampling through HDX: one-sided HDX, sampling and MCMC algorithms, sampling independent sets
- Weeks 9-10 - Topological HDX: topological overlapping property, homology and cohomology, coboundary and cosystolic expanders, applications in hardness of approximation
Notes
We are preparing lecture notes. Please note that they will be updated throughout the quarter.
To download the current version, go on
overleaf and download the pdf (by clicking
this button).
If you spot any typos/errors, or anything is unclear, please let us know.
Lecture videos
- Lecture 1 (3/30): definitions of expansion, expander mixing lemma [video]
- Lecture 2 (4/1): Cheeger inequality [video]
- Lecture 3 (4/6): Finishing the proof of Cheeger inequality, starting random walks on expanders [video]
- Lecture 4 (4/8): Random walks on expanders [video]
Material
Here is some related material that might be useful:
- A class on high-dimensional expanders by Irit Dinur.
- A survey paper on expander graphs by Shlomo Hoory, Nati Linial and Avi Wigderson. It starts with core notions, and then discusses several CS applications.
- A lecture by Avi Wigderson on applications of expanders.
- A survey paper on high-dimensional expanders by Alex Lubotzky, accompanying his ICM 2018 plenary talk. It has an algebraic focus.
