# CS229r: Spectral Graph Theory in Computer Science Semester: Fall | Year offered: 2020 [**The webpage for offerings after 2020 is here.**](https://sites.google.com/g.harvard.edu/sgt/home) 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](/file_url/323) - [Schedule, Lecture Notes, Assignments](/classes/spectral-graph-theory/schedule) - [Guidelines for Reading, Commenting, and Participation](/file_url/325) - [Final Project Guidelines](https://docs.google.com/document/d/1GYJg403lNHDR9_S7q7aSD1s2Jr_KzYpE_SkEF8bvaKk/edit?usp=sharing) - [Q evaluation](/file_url/481) - [Piazza](http://piazza.com/harvard/fall2020/cs229r) (for announcements, communication with course staff, and Q&A) - [Perusall](https://app.perusall.com/courses/spectral-graph-theory-in-cs-fall-2020/_/dashboard/) (social e-reader for readings) - [Canvas](https://canvas.harvard.edu/courses/74674) (for zoom links and recordings, and other material restricted to Harvard students) --- ## Class Materials: ### Schedule, Lecture Notes, and Assignments SortSort**Date** **Title** **Reading** **Lecture Notes** **Assignments & Other Handouts** ## **1. Introduction** Aug 20 Course overview [ whiteboard](/file_url/324) [syllabus](/file_url/321), ps0 due 9/11 ([pdf](/file_url/319), [tex](/file_url/327)) Sep 3 Graphs, matrices, spectral theorem Spielman, Ch. 1-2 [whiteboard](/file_url/326), [scribe notes](/file_url/347) Sep 8 Connectivity, graph drawing, interlacing, graph coloring Spielman, Ch. 3-4 [whiteboard](/file_url/329), [scribe notes](/file_url/348) Sep 10 Cayley graphs Trevisan, Ch. 16; Spielman Ch.7 [whiteboard](/file_url/330), [scribe notes](/file_url/349) ps1, due 9/25 ([pdf](/file_url/334), [tex](/file_url/332)) ## **2. Markov Chains** Sep 15 Cayley graphs (cont.), Random walks on undirected graphs Spielman, Sec. 4.5, Ch. 10 [whiteboard](/file_url/337), [scribe notes](/file_url/339) Sep 17 Random walks on undirected graphs (cont.) Spielman, Sec. 4.5, Ch. 10 [whiteboard](/file_url/335), [scribe notes](/file_url/350) Sep 22 Random walks on directed graphs, Pagerank, and MCMC Babai Ch.8, Madry lecture notes [whiteboard](/file_url/336), [scribe notes](/file_url/351) ## **3. Partitioning and Clustering** Sep 24 Graph coloring, isoperimetry Spielman, Sec 19.5, Ch. 20 [whiteboard](/file_url/338), [scribe notes](/file_url/366) ps2 ([pdf](/file_url/342), [tex](/file_url/343)), due 10/9 Sep 29 Cheeger's Inequality Spielman Ch. 21 [whiteboard](/file_url/340), [scribe notes](/file_url/367) Oct 1 Higher-order Cheeger Trevisan Chs. 7-8 [whiteboard](/file_url/341) Oct 6 The Power Method Trevisan Sec. 9.3 [whiteboard](/file_url/344), [scribe notes](/file_url/373) ## **4. Expander Graphs** Oct 8 Measures of expansion Vadhan Sec. 4.1 [whiteboard](/file_url/345), [scribe notes](/file_url/374) ps3 ([pdf](/file_url/346), [tex](/file_url/352), [psheader.tex](/file_url/355), [macros.tex](/file_url/356)), due 10/23 Oct 13 Measures of expansion (cont.) Vadhan Sec 4.1 [whiteboard](/file_url/354), [scribe notes](/file_url/379) Oct 15 Expansion of random graphs, random walks on expanders Vadhan Sec. 4.1-4.2 [whiteboard](/file_url/353) Oct 20 Explicit constructions, Undirected Connectivity in logspace Vadhan Sec. 4.3-4.4 [whiteboard](/file_url/362), [slides](/file_url/365), [scribe notes](/file_url/381) ## **5. Effective Resistances and Spectral Sparsification** Oct 22 Resistor networks Spielman Sec, 11.7-12.4 [whiteboard](/file_url/364), [scribe notes](/file_url/388) ps4 ([pdf](/file_url/361), [tex](/file_url/368), due 11/17) Oct 27 Schur complements Spielman Sec. 12.5-12.8 [whiteboard](/file_url/363), [scribe notes](/file_url/387) Oct 29 The Matrix-Tree Theorem Spielman Ch. 13 [ whiteboard](/file_url/384) Nov 3 Spectral approximation Spielman Ch. 5 [whiteboard](/file_url/385) Nov 5 Spectral sparsification Spielman Ch. 32 [whiteboard](/file_url/386) Detailed Project Description due Nov 8 ## **6. Solving Laplacian Systems** Nov 10 Iterative methods for linear systems Spielman Ch. 34-Sec. 35.2 [ whiteboard](/file_url/376) Nov 12 Preconditioned iterative methods Spielman Sec. 36.0-36.5 [whiteboard](/file_url/377) Nov 17-19 NO CLASS - [FOCS](https://focs2020.cs.duke.edu/) & [TCC](https://www.iacr.org/workshops/tcc/) conferences Nov 24 A preconditioner from squaring and sparsification Murtagh Ch. 2 [whiteboard](/file_url/392) Problem Set 5 ([pdf](/file_url/391), [tex zip](/file_url/389), due 12/4) Nov 26 NO CLASS - THANKSGIVING Dec 1 Faster max flow via electrical flows Vishnoi Sec. 8.2 ## 7**. Wrap Up** Dec 3 High-dimensional expanders and sampling spanning forests Dec 8 Conclusions and survey of other topics Dec 9 Final project draft papers due Dec 11 Final project presentations Dec 14 Final project presentations Dec 16 Final project revised presentations due --- Attachments- [ picture\_as\_pdf ps5 ](/sites/g/files/omnuum4266/files/salil/files/cs229r-fall20-ps5v2.pdf) - [ picture\_as\_pdf cs229r\_nov\_24\_2020.pdf ](/sites/g/files/omnuum4266/files/salil/files/cs229r_nov_24_2020.pdf) ---