671 Expanders and High-dimensional Expanders

Instructor: Siqi Liu

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

1. Spectral expansion and combinatorial expansion. Overview of applications of expanders. Cheeger's inequality part 1.

2. Cheeger's inequality part 2. Cayley graphs and their expansion. The zig-zag product.

3. Two proofs of the Alon-Boppana bound.

4. The expander mixing lemma. Application to Tanner codes.

5. Rapid mixing of random walks. Application to derandomization.

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

7. Local-spectral HDXs. The trickle-down theorem. Random-walk HDXs.

8. Equivalence of the two types of HDXs. Application to matroid basis sampling.

9. Application to agreement tests.

10. Constructions of local-spectral HDXs: combinatorial and algebraic.

11. Coboundary HDXs and their applications to topological overlapping and agreement tests. Dense constructions of coboundary HDXs and the cone method.

12. Cosystolic HDXs and the local-to-global theorem for cosystolic expansion.

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]