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