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:

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.

More topics:

* Higher order expander mixing lemma, more random walks (the "complement walk").
* isoperimetric inequalities
* quantum (locally testable) codes
* almost diameter and cuttoff
* directed random walks