Tentative Schedule

This schedule is very preliminary: the number of lectures and order of the topics are likely to change.

Lec. Date Day Topic Notes
1 Sep 12 M Introduction and Course topics, Introduced Graph Laplacian, Effective Resistance, and Random Walks. First Day of Class
2 Sep 14 W Resistance, Energy and Rayleigh's Monotonicity Law, and Commute Time
3 Sep 16 F Random Walks, Mixing Rates, and Eigenvectors Hwk 1 out [PDF]
4 Sep 19 M Random Walks, Mixing Rates, and Coupling
5 Sep 21 W Mixing and Bounding Lambda_2 for Laplacians using path embedding.
6 Sep 23 F Diffusion, Spring-Mass Systems, Laplacians, and Matrix Exponentials
7 Sep 26 M Solving Linear Systems and Nested Dissection
8 Sep 28 W More Nested Dissection, Minimum Degree Heuristic, and Fractals
9 Sep 30 F Eigenvalues of directed graphs and the Perron-Frobenius Theorem Hwk 1 due (Solutions PDF)
10 Oct 03 M Graph Cuts and Eigenvalues: Cheeger inequality
Hwk 2 out [PDF]
11 Oct 05 W The Cheeger inequality Continued
12 Oct 07 F Guest Lecture by Nick Harvey: Gragh Maximum Cut
13 Oct 10 M Solving Linear Systems: The Basic Iterative Method, Extrapolated Method, Chebyshev acceleration
14 Oct 12 W Conjugate Gradient Method and Steepest Descent
15 Oct 14 F Conjugate Gradient Method and Steepest Descent Continued
16 Oct 17 M Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees Hwk 2 due (Solutions PDF)
Hwk 3 out [PDF]
17 Oct 19 W Ahlswede-Winter Thm, Graph Sparsification and Effective resistance
Oct 21 F Mid-Semester Break
Oct 24 M FOCS Conference
18 Oct 26 W Proof of Ahlswede-Winter Thm
19 Oct 28 F O(m log n) Lapacian Solver
20 Oct 31 M O(m log n) Lapacian Solver: Continued Hwk 3 due (Solutions PDF)
21 Nov 02 W Fiedler's Thm and Generalized Laplacian's
22 Nov 04 F Spectral Methods for Planar Separators Hwk 4 out [PDF]
23 Nov 07 M Eigenvalues and Vectors by Iterative Methods
24 Nov 09 W Fiedler's Thm Continued and Planar Embeddings
25 Nov 11 F Arnoldi Iteration and Lanczos Algorithm
26 Nov 14 M Arnoldi Iteration and Lanczos Algorithm and Symmetric Diagonally Dominate Systems
27 Nov 16 W Eigenvalues and Vectors for Symmetric Tridiagonal Systems
28 Nov 18 F Counting and Generating Random Spanning Trees
29 Nov 21 M Generating Random Spanning Trees Hwk 4 due (Solutions PDF)
Nov 23 W Thanksgiving Holiday
Nov 25 F Thanksgiving Holiday
30 Nov 28 M Faster Random Walks and Generating Random Spanning Trees
31 Nov 30 W Spectral Rounding
[ ]
32 Dec 02 F Random Walks with Restarts
33 Dec 05 M Maximum Flow via Electrical Flow
34 Dec 07 W Shortest Paths via Interior Point Methods
35 Dec 09 F Homework Review
[ ]
Last Day of Class