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 the problem of approximating graphs by sparse graphs.
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 algorithms play in the design of fast algorithms for solving
Laplacian linear equations.
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 at Yale University. He is presently
the Henry Ford II Professor of Computer Science, Mathematics, and
Applied Mathematics.