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.