University of Illinois at Urbana-Champaign Block I logo
university of illinois at urbana-champaign

Department of Computer Science

Computer Science Department Master Calendar

skip to events

calendar tabs

  •  All 
  • Grid
  • Month
  • Week
  • Day
  • (Selected tab) Detail

Event Detail Information

Event Detail Information

Dr. Dan Spielman, "Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations"

Speaker Dr. Dan Spielman, Yale University
Date Mar 11, 2013
Time 4:00 pm  
Location 2405 Siebel Center
Sponsor The Department of Computer Science, University of Illinois
Event type Donald B. Gilles Lecture
Views 2863

Bio:  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 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, an inaugural Simons Invesigator 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, graph theory, machine learning, error-correcting codes and combinatorial scientific computing.

Abstract:  In 1990, Pravin Vaidya, then a professor of Computer Science at UIUC, discovered a remarkable application of graph theory to the problem of solving systems of linear equations.  We survey several fascinating concepts and algorithms inspired by and related to this work.

These algorithms provide nearly linear time algorithms for solving linear equations in the Laplacian matrices of graphs.
We will begin by explaining why linear equations in these matrices are so interesting.

The problem of solving linear equations in these matrices motivates a new notion of what it means for one graph to approximate another.
This leads to the problem of approximating graphs by sparse graphs.
Our algorithms for solving Laplacian linear equations will exploit surprisingly strong approximations of graphs by sparse graphs, and even by trees.

We will survey the roles that spectral graph theory, random matrix theory, graph sparsification, low-stretch spanning trees and local clustering algorithms play in the design of fast algorithms for solving Laplacian linear equations.