# 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:

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