Date
Topic & Lecture Notes
Assignments
Supplementary Reading
Mon 1/26
Course overview.
Spectrum of the adjacency matrix. lec1-postlec.pdf
First class survey
PS0, ps0.tex, preamble.tex (due Fri 2/6)
Wed 2/11
Markov Chain Monte Carlo
Mon 2/16
No class (President's Day)
Wed 2/18
The Laplacian
Mon 2/23
Conductance and Cheeger's Inequality
ps2, ps2.tex (due 3/6)
Wed 2/25
Proof of Cheeger, and statements of some Cheeger variants
Mon 3/2
The Power Method
Wed 3/4
Measures of expansion
& expansion of random graphs
Mon 3/9
Applications of expanders &
random walks on expanders
ps3, ps3.tex (due Mon 3/30)
Wed 3/11
Explicit constructions of expanders
Form a project group and submit revised topic ideas (due Wed 4/1)
Mon 3/16
No class (Spring break)
Wed 3/18
No class (Spring break)
Mon 3/23
Zig-zag proof, Undirected S-T Connectivity in Logspace
Wed 3/25
Resistor networks,
Schur complements
Mon 3/30
Matrix-Tree Theorem,
leverage scores
Wed 4/1
Spectral sparsification
Detailed project description (due Fri 4/10)
Mon 4/6
Iterative methods for solving linear systems
ps4, ps4.tex (due 4/17)
Wed 4/8
Square-sparsification and efficient Laplacian solvers
Mon 4/13
TBD
Wed 4/15
TBD
Mon 4/20
TBD
Draft project papers due Fri 5/1
Wed 4/22
TBD
Mon 4/27
TBD
Wed 4/29
Conclusions
Fri 5/8
Project presentations
Revised project papers due Tue 5/12