TITLE:
 
Algorithm Design using Spectral Graph Theory
 
ABSTRACT:
 
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 also becoming increasingly popular in
combinatorial optimization, computer vision, computer graphics and
machine learning.
 
This talk will give an overview of some progress on the solver
algorithm, including a sequential algorithm for solving SDD linear
systems in O(m log n log(1/epsilon)) expected time and some steps
towards its parallelization. Some ongoing work on using the solver to
generate faster algorithms for problems such as multicommodity flow
and image denoising problems will also be presented.
 
Topics in this talk represent joint work with Guy Blelloch, Hui Han
Chin, Anupam Gupta, Jon Kelner, Yiannis Koutis, Aleksander Madry, Gary
Miller and Kanat Tangwongsan.