Course description
Spectral graph algorithms are very popular in theoretical computer science and machine learning, as they provide polynomial-time approximations to several hard computational problems. This course covers some basic topics in spectral graph theory and algorithms, with applications to network analysis. The course emphasises rigorous analysis of algorithms.
Registration
Course discussions were held on Piazza.
Assignments
- Assignment 1 (due February 11).
Lectures
| Date | Topic |
|---|---|
| January 5 | Organizational meeting |
| January 13 | Eigenvalues and eigenvectors of a matrix |
| January 15 | Eigenvalues and eigenvectors (contd.) |
| January 17 | Spectral radius; the Gershgorin theorem; the first eigenvalue and the maximum degree of a graph |
| January 22 | Graph colouring; Wilf's theorem; matrices associated with a graph; properties of the Laplacian |
| January 24 | The Laplacian and spectra of simple graphs |
| January 29 | The Courant–Fischer and Perron–Frobenius theorems |
| January 31 | Symmetric matrices; more spectral properties of adjacency and Laplacian matrices |
| February 5 | Cheeger cuts, ratio cuts, normalized cuts and spectral relaxations |
| February 7 | Cheeger's inequality and spectral clustering |
References
- A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, 2011.
- R. Kannan and S. Vempala, Spectral Algorithms, Now Publishers, 2009.