CO759 Algorithms and Spectral Graph Theory - Spring 2014

Announcements

Course Info

For a superb overview of the subject see the maestro's talk on Laplacian Gems: (slides of talk at FOCS 2010) or (video of talk at FOCS 2010) or 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.)

Time & Place

11:30-12:50pm Tue, Thu, MC 6486 (First meeting: May.6 Tue)
MC 6486 is the C&O dept. seminar room.

Instructor

J.Cheriyan, MC6026, phone: 35591 Office Hours: TBA

Prerequisites

Familiarity with algorithms, graphs, and linear algebra, at the undergraduate level. While the background knowledge is elementary, the course will move at a fast pace.

Auditing

by students is discouraged -- please discuss with instructor if there are reasons for auditing.

Grading scheme (Tentative and Negotiable)

Assignments		50%
Project			50%

Lecture Contents (Tentative)

TBA

Texts, Monographs, Lecture Notes, Other Courses

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) and Nikhil Srivastava (MSR)
CS 521: Advanced Algorithm Design, Spring 2012

Projects

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.

Assignments

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

Papers and more Lecture Notes

Matrices, Laplacians, ...

Harvey's notes on Symmetric Matrices, W12 (PDF)

Harvey's notes (scribed) on Graph Laplacians, W13 (PDF)

Cheeger's Inequality

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)

Random Walks ...

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)

Spectral Sparsification of Graphs by Electrical Resistances

Spielman and Srivastava, Graph Sparsification by Effective Resistances

(SICOMP 2011)

Srivastava, slides of talk (PDF)

Expander Graphs

Shlomo Hoory, Nathan Linial and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006), 439-561

Conjugate Gradient Method

J.R.Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (Aug.1994)