CSE 599s: Modern Spectral Graph Theory (Winter 2022)

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 will be submitted via Gradescope.

Class Mailing list: cse599s_wi22

Related Courses

Similar courses at other schools
  • In-class notes lectures 2-5.

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