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

- Lectures: Tuesdays / Thursdays 11-12:20
- Office hours: Shachar - Fridays 10-11am; Max - Tuesday 12:30-1:30

- 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 will be based on homeworks and a final project. Both can be solved individually or in pairs.

- Homework 1, due April 19 11:59pm.
- Homework 2, due May 3 11:59pm.
- Homework 3, due May 24 11:59pm.
- Homework 4, due June 11 11:59pm.

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