Algorithms, Graph Theory and the Solution of Laplacian Linear Equations

Get the Flash Player to see this video.

Wed Aug 24 15:30:00 EDT 2011

We survey several fascinating concepts and algorithms in graph theory that arise in the design of fast algorithms for solving linear equations in the Laplacian matrices of graphs. We will begin by explaining why linear equations in these matrices are so interesting.

The problem of solving linear equations in these matrices motivates a new notion of what it means for one graph to approximate another. This leads to a problem of graph sparsification--the approximation of a graph by a sparser graph. Our algorithms for solving Laplacian linear equations will exploit surprisingly strong approximations of graphs by sparse graphs, and even by trees.

We will survey the roles that spectral graph theory, random matrix theory, graph sparsification, low-stretch spanning trees and local clustering algorithm play in the design of fast algorithms for solving Laplacian linear equations.



Dan Spielman

Daniel Alan Spielman received his B.A. in Mathematics and Computer Science from Yale in 1992, and his Ph.D in Applied Mathematics from M.I.T. in 1995. He spent a year as a NSF Mathematical Sciences Postdoc in the Computer Science Department at U.C. Berkeley, and then taught in the Applied Mathematics Department at M.I.T. until 2005. Since 2006, he has been a Professor of Applied Mathematics and Computer Science at Yale University.

The awards he has received include the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 Godel Prize, the 2009 Fulkerson Prize and the 2010 Nevanlinna Prize. His main research interests include the design and analysis of algorithms, graph theory, machine learning, error-correcting codes and combinatorial scientific computing.