671 Expanders and High-dimensional Expanders

Instructor: Siqi Liu (sl2195@rutgers.edu)

Course description:

The purpose of this course is to offer a graduate level introduction to expanders and high-dimensional expanders. Expanders are sparse and well-connected graphs that have been studied intensively and applied broadly in computer science for decades. In the first half of the course we will study constructions of sparse expanders and explore their connections to coding theory, sampling, and pseudorandomness. In the second half of the course we will consider the generalization of expansion to hypergraphs. We will introduce several different definitions of high-dimensional expanders and take a closer look at spectral, combinatorial, and topological properties and also their applications to sampling and property testing.

Prerequisites:

This is intended as an introductory graduate course. Students should have prior exposure to linear algebra, probability, discrete math, and computational complexity theory. Students should be mathematically mature and will be expected to write proofs and read research papers.

Course Syllabus (tentative)

1. Spectral expansion, combinatorial expansion, Cheeger's inequality, and an overview of applications of expanders

2. Explicit constructions: MGG construction, zig-zag construction, and application to codes

3. Randomized constructions: Erdős-Rényi, random d-regular graphs, random Cayley graph, Gromov's random graph

4. Application to codes: Tanner codes

5. Application to derandomization

6. Expansion in continuous space: diffusion, Laplace operator, and Poincaré inequality

7. Local-spectral high-dimensional expanders and the trickle-down theorem

8. Application to matroid basis sampling

9. Constructions: Kaufman-Oppenheim HDXes, and Linial-Meshulam random complexes

10. Higher order random walks and agreement tests

11. Locally testable codes and the left-right Cayley complex

12. Coboundary and cosystolic high-dimensional expanders: constructions and applications

Grading

1. Homework assignments: 60%, 3 homework assignments in total. Assignments need to be written in latex and submitted via Gradescope.

2. Final Project: 30%, consisting of an in-class presentation and a final report.

3. Scribing lecture notes: 10%.

References

Expanders related

1. Expander graphs and their application, by Hoory, Linial and Wigderson [pdf]

2. Spectral and Algebraic Graph Theory, by Dan Spielman [pdf]

3. (optional) Higher order Fourier analysis, by Terrence Tao [blog link]

High-dimensional expanders related

1. High Dimensional Expanders, by Alex Lubotzky [pdf]

2. Irit Dinur's past course [course page]

3. (optional) Gil Kalai and Alex Lubotzky's past course [course page]