The 14th Annual Paris C. Kanellakis Distinguished Lecture
"Laplacian Matrices of Graphs: Algorithms and Applications"
Daniel Spielman, Yale University
Thursday, December 11, 2014 at 4:00 P.M.
Room 368 (CIT 3rd Floor)
The Laplacian matrices of graphs arise in many fields including Machine Learning, Computer Vision, Optimization, Computational Science, and of course Network Analysis. They appear when one tries to understand a graph by imagining that it represents a physical object. For example, we may pretend that the edges of a graph are springs, rubber bands, or resistors. To understand the behavior of these physical systems, and in most applications of graph Laplacians, we must either solve systems of linear equations in the graph Laplacian or compute its eigenvectors
We will survey some of the ways Laplacian matrices arise, and will try to provide intuition as to why they are so useful. We will then describe recently developed algorithms that allow us to solve linear equations in and compute eigenvectors of these matrices in time that is nearly linear in their number of non-zero entries. These algorithms exploit approximations of graphs by sparser graphs and by trees. We explain what these approximations are and sketch how they lead to fast algorithms for solving linear equations in Laplacian matrices.
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.
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, 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.
This lecture series honors Paris Kanellakis, a distinguished computer scientist who was an esteemed and beloved member of the Brown Computer Science Department. Paris joined the Computer Science Department in 1981 and became a full professor in 1990. His research area was theoretical computer science, with emphasis on the principles of database systems, logic in computer science, the principles of distributed computing and combinatorial optimization. He died in an airplane crash on December 20,1995, along with his wife, Maria Teresa Otoya, and their two young children, Alexandra and Stephanos Kanellakis.
A reception will follow.
Host: Philip Klein
