The course meets Tuesdays and Thursdays in Rhodes 571 from 10:10-11:25AM. It will also be broadcast to Cornell NYC Tech, Ursa room.
This course will consider connections between the eigenvalues and eigenvectors of graphs and classical questions in graph theory such as cliques, colorings, cuts, flows, paths, and walks. Both older structural results and recent algorithmic results will be presented. Topics to be covered include the matrix-tree theorem, Cheeger's inequality, Trevisan's max cut algorithm, bounds on random walks, Laplacian solvers, electrical flow and its applications to max flow, spectral sparsifiers, and the Colin de Verdiere invariant. Additional topics may include the Arora-Rao-Vazirani algorithm for sparsest cut, sampling spanning trees, and recent higher-order Cheeger inequalities.
| Aug 23 |
Introduction. Warmup: bounds on d-regular Moore graphs of diameter two. (Hoffman-Singleton 1960) |
| Aug 25 |
Eigenvalue basics. (Trevisan, Ch. 1; Lau, Lecture 1) |
| Aug 30 |
Eigenvalue identities. The Perron-Frobenius theorem. Bipartite graphs. (Lau, Lecture 1; Spielman, Lecture 3) |
| Sept 1 |
Eigenvalue interlacing. Bounds on clique and chromatic numbers. (Some notes of Embree; Spielman, Lecture 3) |
| Sept 6 |
Graph Laplacians. Algebraic connectivity. Some easy bounds on bisection and max cut. (Lau, Lecture 2; Cvetković et al, Section 7.4; Mohar and Poljak, Sections 2.1 and 2.5) |
| Sept 8 |
Graph Laplacians and the matrix-tree theorem. (Cvetković et al, Sections 7.1, 7.2; Godsil and Royle, Section 13.2) |
| Sept 13 |
Normalized Laplacians. Cheeger's inequality. (Lau 2012, Week 2) |
| Sept 15 |
Cheeger's inequality cont. Trevisan's bound on the largest eigenvalue. (Lau 2012, Week 2; Lau, Lecture 4) |
| Sept 20 |
Trevisan's spectral approximation algorithm for MAX CUT. (Lau 2012, Week 2; Lau, Lecture 4) |
| Sept 22 |
Computing eigenvectors and eigenvalues. (Trevisan, Chapter 4; Vishnoi, Chapter 8) |
| Sept 27 |
Random walks I: stationary probabilities, convergence, mixing time. (Lau, Lecture 7) |
| Sept 29 |
Electrical flows. Effective resistance, energy. (Lau, Lecture 12) |
| Oct 4 |
More about effective resistance. Random walks II: hitting time, cover time. (Bollobás II.1; Lau, Lecture 12; Motwani, Raghavan 6.3-6.5) |
| Oct 6 |
Low-stretch spanning trees. (Harvey, Cargèse Lecture 1) |
| Oct 11 |
Fall break. |
| Oct 13 |
Iterative methods and preconditioning. (Spielman, Lecture 12; Spielman and Woo 2009) |
| Oct 18 |
A simple combinatorial algorithm for solving Laplacian systems. (Kelner, Orecchia, Sidford, and Zhu 2013; Lau, Lecture 13) |
| Oct 20 |
The multiplicative weights update algorithm. (Arora, Hazan, and Kale 2012) |
| Oct 25 |
Max flow in undirected graphs. (Christiano, Kelner, Mądry, Spielman, and Teng 2010; Lau, Lecture 15) |
| Oct 27 |
Matrix Chernoff bounds. (Harvey, Cargèse Lecture 2) |
| Nov 1 |
Spectral sparsifiers. (Harvey, Cargèse Lecture 3; Lau, Lecture 17; Spielman and Srivastava 2011) |
| Nov 3 |
Matrix multiplicative weights update and deterministic sparsifiers. (Arora and Kale 2016; Kale's 2007 thesis; de Carli Silva, Harvey, and Sato 2015) |
| Nov 8 |
Linear-sized spectral sparsifiers. (Batson, Spielman, and Srivastava 2014; Spielman, Lecture 18) |
| Nov 10 |
Generalized Laplacians, planarity, and the Colin de Verdière invariant. (Godsil and Royle, Sections 1.8, 13.9-13.11; Van der Holst 1995) |
| Nov 15 |
No class. |
| Nov 17 |
Kyng-Sachdeva algorithm overview. (Kyng and Sachdeva 2016) |
| Nov 22 |
Arora-Rao-Vazirani sparsest cut algorithm: Leighton-Rao algorithm. Negative-type metrics. Connection to Cheeger inequalities. (Leighton and Rao 1999; Sudan and W unpublished note) |
| Nov 29 |
Arora-Rao-Vazirani sparsest cut algorithm: The algorithm. Reduction to the Structure Theorem. (Rothvoss 2016 lecture notes; W and Shmoys, Section 15.4; Barak and Steurer 2016 lecture notes) |
| Dec 1 |
Arora-Rao-Vazirani sparsest cut algorithm: Proof of the Structure Theorem. (Barak and Steurer 2016 lecture notes) |
|
Structure Theorem Lecture Remix |
|---|