CSE 291 - Expander graphs and high-dimensional expanders
CSE 291 - Expander graphs and High-Dimensional Expanders, Spring 2021
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.
Instructor: Shachar Lovett, firstname.lastname@example.org
TA: Max Hopkins, email@example.com
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 will be based on homeworks and a final project. Both can be solved individually or in pairs.
Final project instructions:
The project can be done individually or in pairs.
You can choose any topic related to what we covered in class. For example, it can be a technical result we didn't cover
in depth, a related area or an application.
After you choose a topic, please email us to confirm it is an acceptable topic. If you are unsure what topic to choose,
feel free to consult with us in OH or in email.
The length of the survey should be 6-10 pages. Submission will be through gradescope.
The deadline is Friday, June 11. If for some reason you need more time, please contact us to discuss it.
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-Gabber-Galil), Combinatorial constructions (Zig-zag)
Part II: High-Dimensional Expanders (HDX)
Weeks 6-7 - Introduction to HDX: simplicial complexes, local-spectral expanders, trickle down lemma, basic constructions
Week 8 - Random walks on HDX: averaging operators, upper and lower walks, random-walk HDX, different decompositions
Week 9 - Sampling through HDX: one-sided HDX, sampling and MCMC algorithms, sampling independent sets
Week 10 - Topological HDX: topological overlapping property, homology and cohomology, coboundary and cosystolic expanders, applications in hardness of approximation
Lecture notes are
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]
Lecture 5 (4/13): Linear algebra lower bounds, super-concentrators [ video]
Lecture 6 (4/15): Expander codes [ video]
Lecture 7 (4/20): Expansion of the infinite d-regular tree [ video]
Lecture 8 (4/22): Alon-Boppana bound and optimal expanders [ video]
Lecture 9 (4/27): Margulis-Gabber-Galil explicit construction of expanders [ video]
Lecture 10 (4/29): Margulis-Gabber-Galil (contd.) [ video]
Lecture 11 (5/4): Zig-zag product [ video]
Lecture 12 (5/6): High dimensional expanders: basic definitions [ video]
Lecture 13 (5/11): Trickling down theorem, Garland's method [ video]
Lecture 14 (5/13): Trickling down theorem (contd.), sparse local-spectral expanders [ video]
Lecture 15 (5/18): Random-walk expanders (part 1) [ video]
Lecture 16 (5/20): Random-walk expanders (part 2) [ video]
Lecture 17 (5/25): Random-walk expanders (part 3) [ video]
Lecture 18 (5/27): Sampling spanning trees, simplified Alev-Lau [ video] (missing first 15 mins of lecture)
Lecture 19 (6/1): Sampling independent sets, full Alev-Lau [ video]
Lecture 20 (6/3): Spectral independence [ video]
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.