Site menu:

• Information
• Notes
• Project

CS 860: Algorithmic Spectral Graph Theory

Lecture:	Mondays and Wednesdays, 11:00-12:20, DC 2568.
Instructor:	Lap Chi Lau
Office hours:	Mondays, 1-2, DC 1309.

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

The following is an ambitious tentative schedule, with about six lectures on classical results, and three lectures for each recent topic. For a more detailed overview with references, see Chapter 1 of the [course notes].

• Classical Results: Cheeger's inequality, random walks, expander graphs
• Topic 1: Generalizations of Cheeger's inequality and graph partitioning
• Topic 2: Random walks and graph decompositions
• Topic 3: Spectral sparsification and applications
• Topic 4: Semidefinite programming and approximation algorithms
• Topic 5: Cut-matching game and matrix multiplicative update
• Topic 6: High-dimensional expanders and mixing time

References: Notes will be provided. See my previous notes on CS 860 (2022) and CS 860 (2019) for related topics, but this is a major revision of the previous course. See also the project page for further references. Below are links to similar courses at other universities for further reference.

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