|
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
|
- In-class notes lectures 2-5.
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 Sum-of-Squares 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:Left-Right 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: Log-Space 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 |
|