Spectral Algorithms and Spectral Graph Theory

Spectral Algorithms and Spectral Graph Theory

There are a number of great monographs and lecture notes for Spectral Graph Theory. My favourites are:

• Spielman’s lecture notes
• Vishnoi’s monograph

I am teaching a Spectral Graph Theory class at BU. Here is the Fall 2016 version.

A classical source for Spectral Graph Theory is Fan Chung’s book.

Connection to Semidefinite Programming

My preffered way to think about spectral algorithms is through the lens of SDP optimization. See these papers of mine for examples:

• Understanding different random walks as SDP regularization of the eigenvector problem: ICML2011 paper
• Characterization of PageRank as solution to quadratic problem: JMLR 2012 paper
• Balanced graph partitioning using SDPs: part I of this STOC paper