This course introduces spectral graph theory along with applications to theoretical computer science, such as in error-correcting codes, analysis of sampling algorithms, and complexity theory.
Logistics
Instructor. Sidhanth Mohanty (Email me at sidhanth (dot) mohanty (at) northwestern (dot) edu)
When? 11:00 am to 12:20 pm, Tuesdays & Thursdays
Where? Tech LG62
Office Hours. 9:30 am to 11:00 am, Tuesdays & Thursdays, Mudd 3510; also by appointment
Evaluation. Homeworks and final project
Course discussion. Join the Piazza page.
Anonymous feedback. Please leave any feedback you have on the course and my teaching here.
Lecture notes
September 16 | |
September 18 | |
September 23 | |
September 25 | |
September 30 | |
October 2 | |
October 7 | Expander constructions I: Near-Ramanujan graphs via random graphs and lifts |
October 9 | |
October 14 | |
October 16 | |
October 21 | |
October 23 | |
October 28 | |
October 30 |
Future topics (subject to significant revision)
November 4 | Phase transitions in statistical physics |
November 6 | Vignette IV: Spectral condition in Ising models |
November 11 | Weak Poincaré inequalities |
November 13 | Slow-mixing random walks and locally stationary distributions |
November 18 | Spectral hypergraph theory: Kikuchi matrices and hypergraph Moore bound |
November 20 | The KLS conjecture: “every convex body is an expander” |
November 25 | Thanksgiving Break |
November 27 | Thanksgiving Break |
December 2 | Almost-resolution of KLS I: Eldan’s stochastic localization |
December 4 | Almost-resolution of KLS II |
Homeworks
Due Date: October 28 |