Expansion in graphs has been tremendously successful in the past few decades, with connections to many mathematical areas, and a multitude of applications in computer science.
High dimensional expansion is a new topic of study that attempts to generalize expansion to graphs with higher dimension.
We will introduce several definitions of high dimensional expansion, and several (quite amazing) constructions coming mainly from group theory.
We will then move to explore connections between these objects and more classical computer science questions, such as
* rapid mixing of MArkiv chains
* locally testable codes
* probabilistically checkable proofs
Lecture 1-2: HDX spectral expansion; link expansion, up-down operators, double sampler. Spectral analysis of expansion in graphs and bipartite graphs ?
Lecture 3: Rapid mixing of Markov chains and relation to HDX
Lecture 4: Coboundary expansion definition and the complete complex
Lecture 5: Local testing and high dimensional expansion (A certain type of property testing how it relates to high dimensional expansion)
Lecture 6: Chain complexes, homology, cohomology, expansion, and quantum LDPC codes
Lecture 7: locally testable codes and the left-right Cayley complex
Lecture 8: Constructions of HDX from group theory: Kaufman-Oppenheim
Lecture 9: Constructions of HDX from group theory: LSV Ramanujan complexes
Lecture 10: PCPs and hardness of approximation
Lecture 11: Parallel repetition and agreement testing
Lecture 12: The Grassman complex and the 2:2 theorem
Lecture 13: Open directions
* complement random walk and expander mixing lemma
* Sos lower bounds for 3LIN through cohomological expansion
* Fourier analysis on HDX
* combinatorial constructions of HDX