High dimensional expanders - Fall 2018 course

High dimensional expanders (HDX) - Fall 2018 course

Lecturer: Irit Dinur
Location: Math 2 building, room 108
Time: Mondays 11:15 - 14:00
TA: Yotam Dikstein

Expander graphs are sparse graphs that are highly connected. They are very interesting mathematically and have applications in many areas of computer science: from computational complexity through network algorithms to error correcting codes. 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.

[Project signup] ; [Template] for scribers; [Exercise 1] [Exercise 2]

Here is a tentative plan for the lectures in the course:

Nov 4: [scribe by Yoni Akkerman and Yotam Dikstein] Introduction to high dimensional expanders. Spectral expansion in (weighted) graphs. Simplicial complexes and their links. Spectral link expansion. Local to global.
Nov 11: [scribe by Yotam Dikstein] Construction of expander graphs: the zigzag product (guest lecture by Yotam Diskstein).
Nov 18: [scribe by Boaz Menuhin] Lazy and non-lazy random walks on complexes. Relation to the up-down operators. Alternative definition of expansion based on random walks.
Nov 25: [scribe by Gal Yehoshua] The flags complex (aka spherical building) - combinatorial description and analysis of link expansion.
Dec 3: [scribe by Limor Friedman] Groups, Cayley graphs and Expanders. Epsilon-biased distributions and error correcting codes.
Dec 10: [scribe by Dafna Sadeh] Error correcting codes, local testing, and high dimensional expansion
Dec 24: [scribe by Boaz Menuhin] Boundary and coboundary operators; cohomology and homology in complexes. Coboundary expansion. Motivations: Topological overlap property, and random high dimensional complexes.
Dec 31: [scribe by Inbal Livni Navon] Harmonic analysis on the Boolean cube and beyond (guest lecture by Yuval Filmus). Survey of results in Boolean function analysis and how these extend to other domains such as the slice (aka the complete complex) and the Grassmann.
Jan 7: [scribe by Irit Dinur] Locally testable codes and coboundary expansion. Coboundary expansion of the complete complex, locally testable codes and linearity testing, PCPs as constraint expanders.
Jan 14: [scribe by Yotam Dikstein] Harmonic analysis on HDX (guest lecture by Yotam Dikstein). Appoximate eigenvalues and eigenspaces. Sequentially differential posets and ASDs. Example: the Grassmann.
Jan 21: [notes] Group theoretic construction of HDX (Kaufman-Oppenheim)
Jan 28: [scribe] Agreement testing (A concept that comes from PCPs yet relates to high dim expansion and to local testing)
Feb 4: [scribe by Omer Lavy] Double samplers, even more mixing random walks on high dimensional expanders

Related material:

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