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 Home National Science Foundation - Computer & Information Science & Engineering (CISE)
Computer & Information Science & Engineering (CISE)
design element
About CISE
Funding Opportunities
Advisory Committee
Career Opportunities
Advisory Committee for Cyberinfrastructure
See Additional CISE Resources
View CISE Staff
CISE Organizations
Advanced Cyberinfrastructure (ACI)
Computing and Communication Foundations (CCF)
Computer and Network Systems (CNS)
Information & Intelligent Systems (IIS)
Proposals and Awards
Proposal and Award Policies and Procedures Guide
Proposal Preparation and Submission
bullet Grant Proposal Guide
  bullet Grants.gov Application Guide
Award and Administration
bullet Award and Administration Guide
Award Conditions
Merit Review
NSF Outreach
Policy Office
Additional CISE Resources
Assistant Director's Presentations and Congressional Testimony
CS Bits & Bytes
CISE Distinguished Lecture Series
Cyberlearning Webinar Series
Data Science Webinar Series
Smart & Connected Health Webinar Series
WATCH Series
CISE Strategic Plan for Broadening Participation
Keith Marzullo on Serving in CISE
Cybersecurity Ideas Lab Report
Other Site Features
Special Reports
Research Overviews
Multimedia Gallery
Classroom Resources
NSF-Wide Investments

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