We survey recent advances in the design of algorithms for solving linear equations in the Laplacian matrices of graphs. These algorithms motivate and rely upon fascinating concepts in graph theory, the most important of which is a definition of what it means for one graph to approximate another. This definition leads to the problem of sparsification: the approximation of one graph by a sparser graph.

The sparsest possible approximation of a graph is a spanning tree. The average stretch of a spanning tree will be revealed to be a good measure of its approximation quality. We explain how every graph on n vertices can be well-approximated by a graph with O (n) edges. To solve linear equations, we will require something in between: approximations by graphs with n + O (n / log n) vertices. To build these sparse approximations, we employ low-stretch spanning trees, random matrix theory, spectral graph theory, and graph partitioning algorithms.

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 and the 2009 Fulkerson Prize. His main research interests include the design and analysis of algorithms, graph theory, machine learning, error-correcting codes and combinatorial scientific computing.