<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 12pt; color: #000000'><b>Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations</b>
<br>
<b><a href="http://cs-www.cs.yale.edu/homes/spielman/">Dan Spielman</a></b>, <a href="http://www.yale.edu/">Yale University</a>
<br>Thursday, November 29, 4:30pm<br>Computer Science 105<br>
<br>
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.
<p>
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. <br></p><p><br></p><p>
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. <br></p><p><br></p><p>
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. <br></p><p><br></p>
He has received many awards, including the 1995 ACM Doctoral Dissertation
Award, the 2002 IEEE Information Theory Paper Award, the 2008 Godel
Prize, the 2009 Fulkerson Prize, the 2010 Nevanlinna Prize, an
inaugural Simons Invesigator Award, and a MacArthur Fellowship. He is
a Fellow of the Association for Computing Machinery and a member of
the Connecticut Academy of Science and Engineering. His main research
interests include the design and analysis of algorithms, graph theory,
machine learning, error-correcting codes and combinatorial scientific
computing.
<div><br><span name="x"></span><br></div><br></div></body></html>