For a superb overview of the subject see
the maestro's talk on Laplacian Gems:
(slides of talk at FOCS 2010)
(video of talk at FOCS 2010)
the talk at ICM 2010
(slides of talk at ICM 2010)
(PS: Comments from crediting students on topics
for coverage are welcome -- please email or discuss in person.)
Assignments 50% Project 50%
Chris Godsil and Gordon Royle, Algebraic Graph Theory, Springer 2001 ( publisher's page).
Fan Chung, Spectral Graph Theory, AMS 1997 ( author's page).
Ravi Kannan and Santosh Vempala, Spectral Algorithms, NOW 2009 ( publisher's page).
Nisheeth Vishnoi, Lx = b, Laplacian Solvers and Their Algorithmic Applications, Foundations and Trends in Theoretical Computer Science, 8:1-2, 2012 ( author's page).
Daniel Spielman (Yale),
CS 662 / AM 561 : Spectral Graph Theory, Fall 2012
Daniel Spielman (Yale),
CS 662 / AM 561 : Spectral Graph Theory, Fall 2009
Nick Harvey (UBC),
CPSC 536N: Sparse Approximations, Winter 2013
Jonathan Kelner (MIT),
18.409 Topics in Theoretical Comp Science, Fall 2009
Lap Chi Lau (CUHK),
CSC 5160: Spectral Algorithms, Spring 2012
James Lee (UW),
CSE 599S: Algorithmic Spectral Graph Theory, Spring 2012
Luca Trevisan (Stanford),
CS 359G: Graph Partitioning and Expanders, Winter 2011
CS 366: Graph Partitioning and Expanders, Winter 2013
Sanjeev Arora (Princeton)
Nikhil Srivastava (MSR)
CS 521: Advanced Algorithm Design, Spring 2012
Schedule of talks, with links to summaries (PDF, 2-pages) and papers
Project reports are due by Aug.23 (Sat) -- if possible, please typeset using restricted-LaTeX, as described here.
Students are expected to write up solutions on their own. All hints, collaboration, outside help etc. should be explicitly listed in the submission.
Assignment 1, due May. 30 (Fri) in office MC6026 or mailbox, PDF, 3 pages
Harvey's notes on Symmetric Matrices, W12 (PDF)
Harvey's notes (scribed) on Graph Laplacians, W13 (PDF)
Kelner's course (MIT 18.409 F2009) lecture 3 (PDF)
(if the link is failing, go to the course webpage and try from there)
Spielman's course (MIT "Applied Extremal Combinatorics" F1998) lecture 5 (postscript)
Trevisan's course (Stanford CS359G W2011) lecture 4 (PDF)
Lau's course (CUHK CSC5160 S2012) week 2 ... for Normalized Laplacians (PDF)
P.G.Doyle and J.Laurie Snell, Random Walks and Electric Networks, (A popular account of the connection between random walks and electric networks (1984).)
David Aldous and James Allen Fill, Reversible Markov Chains and Random Walks on Graphs, (unfinished monograph, 1990s)
Spielman and Srivastava, Graph Sparsification by Effective Resistances
Srivastava, slides of talk (PDF)
Shlomo Hoory, Nathan Linial and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006), 439-561
J.R.Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (Aug.1994)