Spectral Graph Theory is the interplay between linear algebra and combinatorial graph theory. Laplace's equation and its discrete form, the Laplacian Matrix, appears ubiquitously in mathematical physics.

Due to the recent discovery of very fast solvers for these equations, they are becoming increasingly popular in combinatorial optimization, computer vision, computer graphics and machine learning.

This talk will give an overview of our solver algorithms, including a sequential algorithm for solving Symmetric Diagonally Domiate (SDD) linear systems in O(m log n) expected time to constant precision. We will also discus parallel versions of the solver with near linear work.

The talk will be motivated by considering the classic problem of image denoising. More recent convex formulations of this problem will natural lead us into better algorithms for problems such as approximate multicommodity flow and a faster flow algorithm for graphs with good separator structure.

Topics in this talk represent joint work with Guy Blelloch, Hui Han Chin, Anupam Gupta, Jon Kelner, Yiannis Koutis, Aleksander Madry, Richard Peng and Kanat Tangwongsan.