Schedule, Lecture Notes, and Assignments

Schedule

For preamble.tex go here  

Date

Title

Slides/Notes/HW

Supplementary Reading

Wed 1/18

Course preview

recording, board

Spielman Ch. 1; Lau Ch. 1; Vishnoi

Mon 1/23

Cancelled

PS0, ps0.tex, preamble.tex (due Fri 2/3)

Wed 1/25

Basics and the adjacency matrix

lec1.pdf 

Lau Sec. 3.1; Spielman Ch. 2, Secs. 4.1, 4.2

Mon 1/30

Graph coloring

prelec2.tex, lec2.pdf 

Spielman 4.3, 4.4, 19.5, 19.6

Wed 2/1

The Laplacian and other matrices

prelec3.tex, lec3.pdf, PS1, ps1.tex  (due Fri 2/17)

Lau Sec. 3.2-3.6, Spielman Ch. 3, Spielman Sec. 7.1, 7.2, 7.3

Mon 2/6

Cayley graphs

prelec4.tex, lec4.pdf 

Trevisan Ch. 16, Spielman Ch. 7

Wed 2/8

Random walks on undirected graphs

prelec5.tex, lec5.pdf, sec3.pdf 

Spielman Sec. 4.5, Ch. 10

Mon 2/13

Random walks on directed graphs and Pagerank

prelec6.tex, lec6.pdf 

Babai Ch. 8, Madry Lec. 10

Wed 2/15

Markov Chain Monte Carlo

lec7.pdf, PS2, ps2.tex  (due 3/3), preamble.tex, regular-pi.png  

Lau Sec. 6.4, Spielman Ch. 20

Mon 2/20

No class (President's Day)

Project guidelines 

Wed 2/22

Conductance

lec8.pdf, prelec8.tex, sec5.pdf 

Spielman Ch. 20, Lau Ch. 4

Mon 2/27

Proof of Cheeger, Cheeger Variants

lec9.pdf, prelec9.tex 

Trevisan Ch. 4, Lau Ch. 4-5, Trevisan Ch. 7, Spielman Ch. 21

Wed 3/1

The Power Method

lec10.pdf, prelec10.tex, PS3 , ps3.tex (due 3/24)

Trevisan Sec. 9.3

Mon 3/6

Measures of Expansion

lec11.pdf, prelec11.tex 

Vadhan Ch. 4, Spielman Ch. 27, Lau Ch. 7

Wed 3/8

Expansion of Random Graphs

lec12.pdf, prelec12.tex, Revised project ideas (due 3/22), sec7.pdf 

Vadhan Ch. 4, Trevisan Ch. 20, Spielman Ch. 8

Mon 3/13

No class (spring break)

Wed 3/15

No class (spring break)

Mon 3/20

Random Walks on Expanders

lec13.pdf, prelec13.tex 

Vadhan Sec 4.2

Wed 3/22

Explicit Constructions of Expanders

lec14.pdf,  prelec14.tex, PS4 (due 4/7), ps4.tex 

Lau Sec 7.2

Mon 3/27

Zig-Zag Proof, Undirected S-T Connectivity in Logspace

lec15.pdf,  prelec15.tex, Detailed project proposal (due 3/31)

Vadhan Sec 4.3, 4.4

Wed 3/29

Resistor Networks

lec16.pdf, prelec16.tex, sec9.pdf 

Spielman Ch.12

Mon 4/3

Schur Complements and The Matrix-Tree Theorem

lec17.pdf

Spielman Sec 13.4

Wed 4/5

Leverage Scores, Spectral Approximation

lec18.pdf, PS5, ps5.tex (due 4/21)

Spielman Sec13.5

Mon 4/10

Spectral Sparsification

lec19.pdf,  prelec19.tex 

Spielman Ch. 32

Wed 4/12

Iterative Methods for Linear Systems

lec20.pdf sec11.pdf

Spielman Ch. 34

Mon 4/17

Preconditioners via Squaring & Sparsification

lec21.pdf 

Murtagh Sec 2.3-2.8

Wed 4/19

Square-Sparsification and Fast Max-Flow

lec22.pdf 

Lau Sec 19.1-19.2

Mon 4/24

High-Dimensional Expanders

lec23.pdf 

Lau Sec 19.3, Ch.20

Wed 4/26

Analyzing High-Dimensional Expansion

lec24.pdf 

Mon 5/1

Conclusions

Draft project papers due

Mon 5/8

Project presentations

Wed 5/10

Final project papers due