About the series
Prof. Daniel Spielman, Yale University
I will tell the story of the development of shockingly fast algorithms for fundamental computational problems.
The two main characters, systems of linear equations and graphs (also called networks), have been studied for centuries. They are brought together by the attempt to understand graphs through physical metaphors. Powerful graph analyses are achieved by viewing the links in a graph as resistors, springs, or rubber bands that meet at their vertices. To understand the resulting physical systems, one must solve systems of linear equations in Laplacian matrices.
The effort to design fast algorithms for solving these systems of linear equations has both built upon and inspired exciting developments in graph theory. These include algorithms for clustering vertices in graphs, a definition of what it means for one graph to approximate another, and fast algorithms for approximating graphs by simpler graphs.
BIO:
Daniel A. Spielman is a Professor of Applied Mathematics and Computer Science at Yale University. His research interests include analysis of algorithms, graph theory, machine learning, error-correcting codes and combinatorial scientific computing. His honors include the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 Godel Prize, the 2009 Fulkerson Prize, and the 2010 Nevanlinna Prize. He is a fellow of the ACM.
