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 | |
November 4 | Slow-mixing Markov chains I: Locally stationary distributions |
November 6 | Slow-mixing Markov chains II: Finding large independent sets in triangle-free graphs |
November 11 | Spectral methods in extremal combinatorics: Equiangular lines |
November 13 | |
November 18 | |
November 20 |
Future topics
November 25 | Thanksgiving Break |
November 27 | Thanksgiving Break |
December 2 | Random walks on continuous domains and the KLS conjecture |
December 4 | Eldan’s stochastic localization and almost-resolution of KLS |
Homeworks
Due Date: October 28 | |
Due Date: December 5 |