CS229r: Spectral Graph Theory in Computer Science
The webpage for offerings after 2020 is here.
Spectral graph theory is about how eigenvalues, eigenvectors, and other linear-algebraic quantities give us useful information about a graph, for example about how well-connected it is, how well we can cluster or color the nodes, and how quickly random walks converge to a limiting distribution. Spectral graph theory has turned out to be extremely useful in theoretical computer science, with applications ranging from solving linear systems, converting randomized algorithms to deterministic algorithms, sampling via Markov Chain Monte Carlo, counting, web search, and maximum flow. In this course, we will study both the mathematics and the algorithmic applications of spectral graph theory, including some results from the past couple of years. Along the way, we will cover a number of concepts and tools that are quite broadly useful, such as mixing of Markov chains, expander graphs, algorithmic linear algebra, and the multiplicative weights method for optimization.
Links
- Syllabus
- Schedule, Lecture Notes, Assignments
- Guidelines for Reading, Commenting, and Participation
- Final Project Guidelines
- Q evaluation
- Piazza (for announcements, communication with course staff, and Q&A)
- Perusall (social e-reader for readings)
- Canvas (for zoom links and recordings, and other material restricted to Harvard students)
Class Materials:
Schedule, Lecture Notes, and Assignments
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||