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.
Instructors
Instructor: Shachar Lovett, slovett@ucsd.edu
TA: Max Hopkins, nmhopkin@eng.ucsd.edu
Logistics
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.
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.
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
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.