|
Date
|
Title
|
Reading
|
Lecture Notes
|
Assignments & Other Handouts
|
1. Introduction
|
|
|
|
|
Aug 20
|
Course overview
|
|
whiteboard
|
syllabus, ps0 due 9/11 (pdf, tex)
|
|
Sep 3
|
Graphs, matrices, spectral theorem
|
Spielman, Ch. 1-2
|
whiteboard, scribe notes
|
|
|
Sep 8
|
Connectivity, graph drawing, interlacing, graph coloring
|
Spielman, Ch. 3-4
|
whiteboard, scribe notes
|
|
|
Sep 10
|
Cayley graphs
|
Trevisan, Ch. 16; Spielman Ch.7
|
whiteboard, scribe notes
|
ps1, due 9/25 (pdf, tex)
|
2. Markov Chains
|
|
|
|
|
Sep 15
|
Cayley graphs (cont.), Random walks on undirected graphs
|
Spielman, Sec. 4.5, Ch. 10
|
whiteboard, scribe notes
|
|
|
Sep 17
|
Random walks on undirected graphs (cont.)
|
Spielman, Sec. 4.5, Ch. 10
|
whiteboard, scribe notes
|
|
|
Sep 22
|
Random walks on directed graphs, Pagerank, and MCMC
|
Babai Ch.8, Madry lecture notes
|
whiteboard, scribe notes
|
|
3. Partitioning and Clustering
|
|
|
|
|
Sep 24
|
Graph coloring, isoperimetry
|
Spielman, Sec 19.5, Ch. 20
|
whiteboard, scribe notes
|
ps2 (pdf, tex), due 10/9
|
|
Sep 29
|
Cheeger's Inequality
|
Spielman Ch. 21
|
whiteboard, scribe notes
|
|
|
Oct 1
|
Higher-order Cheeger
|
Trevisan Chs. 7-8
|
whiteboard
|
|
|
Oct 6
|
The Power Method
|
Trevisan Sec. 9.3
|
whiteboard, scribe notes
|
|
4. Expander Graphs
|
|
|
|
|
Oct 8
|
Measures of expansion
|
Vadhan Sec. 4.1
|
whiteboard, scribe notes
|
ps3 (pdf, tex, psheader.tex, macros.tex), due 10/23
|
|
Oct 13
|
Measures of expansion (cont.)
|
Vadhan Sec 4.1
|
whiteboard, scribe notes
|
|
|
Oct 15
|
Expansion of random graphs, random walks on expanders
|
Vadhan Sec. 4.1-4.2
|
whiteboard
|
|
|
Oct 20
|
Explicit constructions, Undirected Connectivity in logspace
|
Vadhan Sec. 4.3-4.4
|
whiteboard, slides, scribe notes
|
|
5. Effective Resistances and Spectral Sparsification
|
|
|
|
|
Oct 22
|
Resistor networks
|
Spielman Sec, 11.7-12.4
|
whiteboard, scribe notes
|
ps4 (pdf, tex, due 11/17)
|
|
Oct 27
|
Schur complements
|
Spielman Sec. 12.5-12.8
|
whiteboard, scribe notes
|
|
|
Oct 29
|
The Matrix-Tree Theorem
|
Spielman Ch. 13
|
whiteboard
|
|
|
Nov 3
|
Spectral approximation
|
Spielman Ch. 5
|
whiteboard
|
|
|
Nov 5
|
Spectral sparsification
|
Spielman Ch. 32
|
whiteboard
|
Detailed Project Description due Nov 8
|
6. Solving Laplacian Systems
|
|
|
|
|
Nov 10
|
Iterative methods for linear systems
|
Spielman Ch. 34-Sec. 35.2
|
whiteboard
|
|
|
Nov 12
|
Preconditioned iterative methods
|
Spielman Sec. 36.0-36.5
|
whiteboard
|
|
|
Nov 17-19
|
NO CLASS - FOCS & TCC conferences
|
|
|
|
|
Nov 24
|
A preconditioner from squaring and sparsification
|
Murtagh Ch. 2
|
whiteboard
|
Problem Set 5 (pdf, tex zip, due 12/4)
|
|
Nov 26
|
NO CLASS - THANKSGIVING
|
|
|
|
|
Dec 1
|
Faster max flow via electrical flows
|
Vishnoi Sec. 8.2
|
|
|
7. Wrap Up
|
|
|
|
|
Dec 3
|
High-dimensional expanders and sampling spanning forests
|
|
|
|
|
Dec 8
|
Conclusions and survey of other topics
|
|
|
|
|
Dec 9
|
Final project draft papers due
|
|
|
|
|
Dec 11
|
Final project presentations
|
|
|
|
|
Dec 14
|
Final project presentations
|
|
|
|
|
Dec 16
|
Final project revised presentations due
|
|
|
|
