text-only page produced automatically by LIFT Text Transcoder Skip all navigation and go to page contentSkip top navigation and go to directorate navigationSkip top navigation and go to page navigation
National Science Foundation
Events Calendar
design element
Events Calendar
Proposal Review Panels

Save the dateEmail this pagePrint this page
CDL - Algorithms, Graph Theory, and Laplacian Linear Equations

CISE Distinguished Lecture Series

November 8, 2011 1:30 PM  to 
November 8, 2011 2:30 PM
Room 375 - NSF

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.


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.

This event is part of Webinars/Webcasts.

Meeting Type

Dawn Patterson, (703) 292-8910, dpatters@nsf.gov

NSF Related Organizations
Directorate for Computer & Information Science & Engineering

Public Attachments
Audio File
Transcript (unedited)


Save the dateEmail this pagePrint this page
Back to Top of page