Site menu:

• Information
• Notes
• Project

CS 860: Algorithmic Spectral Graph Theory

Lecture:	Tuesdays and Thursdays, 10:00-11:20, DC 2568.
Instructor:	Lap Chi Lau
Office hours:	Tuesdays, 2-3, DC 1309.
Course outline:	[pdf]

This course begins with a review of classical results in spectral graph theory, followed by an exploration of several recent developments, with a focus on algorithmic results.

The following is a tentative schedule. For a more detailed overview with references, see Chapter 0 of the [course notes].

• Classical Results: Cheeger's inequality, random walks, expander graphs
• Topic 6: Matrix Concentration, spectral sparsification, CSP refutation, Kikuchi matrices.
• Topic 4: Cut-matching game, matrix multiplicative update, Sherman's algorithm
• Topic 5: Threshold rank decomposition, semidefinite programming, global correlation rounding, reweighing conjecture
• Topic 7: High-dimensional expanders and mixing time

References: Notes will be provided. See my previous notes on CS 860 (2025) for related topics, with different topics covered. See also the project page for further references. Below are links to similar courses at other universities.

• Spectral Graph Theory, by Dan Spielman.
• Mordern Spectral Graph Theory, by Shayan Oveis Gharan.
• Graph Partitioning, Expanders and Spectral Methods, by Luca Trevisan.

CS, Waterloo.