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