DLS: Daniel Alan Spielman - The Laplacian Matrices of Graphs: Algorithms and Applications

Daniel Alan Spielman
Henry Ford II Professor of Computer Science, Mathematics, and Applied Mathematics
Yale University

Abstract

The Laplacian matrices of graphs arise in many fields, including machine learning, computer vision, optimization, computational science, and of course network analysis. We will explain what these matrices are and why they appear in so many applications. We then survey recent ideas that allow us to solve systems of linear equations in Laplacian matrices in nearly linear time, emphasizing the utility of graph sparsification — the approximation of a graph by a sparser one — and a recent algorithm of Kyng and Sachdeva that uses random sampling to accelerate Gaussian Elimination.

Biography

Daniel Alan Spielman received his BA in Mathematics and Computer Science from Yale in 1992, and his PhD in Applied Mathematics from MIT in 1995. He spent a year as a NSF Mathematical Sciences Postdoc in the Computer Science Department at University of California, 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.  

He has received many awards, including the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 and 2015 Godel Prize, the 2009 Fulkerson Prize, the 2010 Nevanlinna Prize, the 2014 Polya Prize, an inaugural Simons Investigator 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, network science, machine learning, digital communications and scientific computing.

Did you miss Daniel Alan Spielman's lecture or would you like to hear it again? If so, just start the video below.