Spectral Graph Theory, the field of analyzing graphs based on the eigenvalues and eigenvectors associated to adjacency matrix, or the (normalized) Laplacian matrix have found abundance of applications in computing from Pseudorandomness, and Coding theory, all the way to approximation algorithms, hardness of approximation and approximate counting and sampling.
In this course, I plan to have a modern take on spectral graph theory. There will be a few sections in the course where in each part I intend to start with classical results and then talk about more recent developments.
Administrative Information
Instructor: Shayan Oveis Gharan
Office Hours: By appointment zoom link.
Lectures: Tue  Thu 11:30  12:50 in G10, lectures will be in person. A recording will be available in Panapto.
Teaching Assistants:
Assignments
Assignments will be submitted via Gradescope.
Class Mailing list: cse599s_wi22
Related Courses
Similar courses at other schools

 Inclass notes lectures 25.
Tentative Schedule:
Lecture  Topic  Notes/Video  Reading 
Lecture 1 (01/04/2022)  Introduction, Random Walks  pdf video  
Lecture 2 (01/06/2022)  I:Spectral Profile  pdf  Expansion Profile and Evolving Sets, Almost Optimal Local Graph Clustering 
(01/11/2022) No lecture (SODA) 
Lecture 3 (01/13/2022)  I:Cheeger's Inequality, Small Set Expansion  pdf, video  Small Set Expansion and Unique Games 
Lecture 4 (01/18/2022)  I:Subexponential Alg for Unique Games  video  
Lecture 5 (01/20/2022)  I:BRS Local to Global Thms  pdf,video  Rounding by SumofSquares Hierarchy 
Lecture 6 (01/25/2022)  II:Coding Theory, Expander Codes  pdf, video  Expander Codes 
Lecture 7 (01/27/2022)  II:Tensor Codes, Local Testability  video  Smooth Codes 
Lecture 8 (02/01/2022)  II:LeftRight Cayley Codes  video  Goldreich's take on Locally Testable Codes 
Lecture 9 (02/03/2022)  II:Proof of DELLM (1)  video  DELLM21 paper 
Lecture 10 (02/08/2022)  II:Proof of DELLM (2)  video  
Lecture 11 (02/10/2022)  III:Simplicial Complexes, Spectral Independence  pdf, video  
Lecture 12 (02/15/2022)  III:Local to Global Thm  video  
Lecture 13 (02/17/2022)  III:Influence Matrix and SAW Tree  video  
(02/23/2022) NO class (Traveling) 
(02/25/2022) NO class (Traveling) 
Lecture 14 (03/01/2022)  III:Finishing the Proof of Mixing of Hardcore Model  video  
Lecture 15 (03/03/2022)  IV: LogSpace Computation Intro, Spectral Approximation  pdf,video  log^(3/2) n space Alg by Saks and Zhou 
Lecture 16 (03/08/2022)  IV: Spectral Approximation in Small Space  video  Deterministic Approximation of RW in Undirected Graphs in Small Space 
Lecture 17 (03/10/2022)  IV: Boosting and Estimating Hitting Probabilities  video  High Precission Estimating of RW in Small Space 
