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