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.

• 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.

• Link: https://ucsd.zoom.us/j/98925366007, or connect with meeting ID 989-2536-6007
• Password: exp***ers (replace *** with correct letters, corresponding to class name)
• Piazza: https://piazza.com/ucsd/spring2021/cse291g (for discussions, announcements, finding team members, etc)
• Gradescope: https://www.gradescope.com (for hw submission). Entry code is RWRZ3D.

Evaluation

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-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

Notes

Lecture notes are here.

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]
• 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]

Material