High dimensional expanders (HDX)

Fall 2022

Lecturer: Irit Dinur
Location: Ziskind 155
Time: Tuesdays 14:15 - 17:00 (first lecture November 8, 2022)
TA: Yotam Dikstein

Expander graphs are sparse graphs that are highly connected. They are related to many mathematical areas, and have a multitude of applications in computer science: from computational complexity through network algorithms to error correcting codes. The topic of high dimensional expansion is relatively new. High dimensional expanders are generalizations of graph expanders to higher dimensions (on hypergraphs or simplicial complexes). There is no one canonical generalization, rather, several different definitions have come about in the past few years. The topic of high dimensional expansion turns out to be of interest to a variery of areas, both math and computer science. We will explore topological, combinatorial, and group theoretic aspects of this topic; as well as applications to computer science.

Homework exercises:  [HW1]   [HW2]
Playlist of lecture videos: [here]

Here is a list of the lectures in the course:

  1. Intro to expanders and high dimensional expanders. Applications to random walks on Markov chains and error correcting codes. Simplicial complexes, walks on them, and links. Random walks on simplicial complexes. [notes]

  2. Definition of high dimensional expansion. Trickle-down: from local expansion to global expansion. Random walks and application to sampling random matroid basis.
    [video] [notes]

  3. Higher order random walks
    [video] [notes]

  4. Topological and Cohomological perspectives on expansion
    [notes] Unfortunately, there was a video recording glitch, but there's an [alternative video]

  5. Cosystolic expansion as a type of property testing. Coboundary expansion of the complete complex, and BLR linearity testing as coboundary expansion of a chain complex
    [notes] [video part 1] [video part 2] [video part 3]

  6. PCPs, locally testable codes, and in particular tensor codes
    [notes] [video]

  7. Constructions of HDX from group theory: Kaufman-Oppenheim (lecture by Yotam Dikstein)
    [notes] [video]

  8. Cosystolic expansion of bounded-degree HDX: A local to global theorem.
    [notes] [video]

  9. Locally testable codes and the left-right Cayley complex
    [notes] [video]

  10. LTCs (cont) and quantum LDPC codes
    [notes] [video]

  11. Tight inapproximability, parallel repetition and agreement tests
    [notes] [video]

  12. Approximate "Fourier" decomposition of functions on HDX
    [notes] [video]
    (the notes are a scribe from Yotam's lecture a couple of years ago)

  13. Hypercontractivity and small set expansion (guest lecturer: Max Hopkins)
    [notes] [video part 1] [video part 2]

  14. Course summary and open directions

Related material: 

* A previous offering of this course.
* A survey paper on expander graphs by Hoory, Linial and Wigderson, and also see this beautiful talk by Avi Wigderson on applications of expanders.
* A course on high dimensional expanders by Alex Lubotzky and Gil Kalai, given at the Hebrew University. There are some really good lecture videos here.
* A course on PCPs and high dimensional expansion offered at Weizmann in 2016. There was much more focus on PCP related material than on HDX.
* A survey paper titled High Dimensional Expanders by Alex Lubotzky, accompanying his ICM 2018 plenary talk.