Schedule, Lecture Notes, and Assignments





Lecture Notes

Assignments & Other Handouts

1. Introduction




Aug 20

Course overview



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



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, texpsheader.texmacros.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



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



Nov 3

 Spectral approximation

Spielman Ch. 5



Nov 5

 Spectral sparsification

 Spielman Ch. 32


Detailed Project Description due Nov 8

  6.   Solving Laplacian Systems


Nov 10

 Iterative methods for linear systems

Spielman Ch. 34-Sec. 35.2



Nov 12

 Preconditioned iterative methods

Spielman Sec. 36.0-36.5



 Nov 17-19    NO CLASS - FOCS & TCC conferences      

Nov 24

 A preconditioner from squaring and sparsification

Murtagh Ch. 2


 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      




CS229r: Spectral Graph Theory in Computer Science

Attach Files: