Spring 2011 Distinguished Lecturer

TTIC is pleased to present our spring 2011 Distinguished Lecturer, Daniel Spielman of Yale University. We hope you can join us for this event. Refreshments will be served after the talk.

When: Monday March 7, 1:30pm

Where: Toyota Technological Institute at Chicago Conference Room 530 (Kenwood Ave. & 61st St.)

Who: Daniel Spielman

Title:
Graph approximation, local clustering, and the solution of systems of linear equations.

Abstract:
We discuss several fascinating concepts and algorithms in graph theory that arose in the design of a nearly-linear time algorithm for solving diagonally-dominant linear systems. We begin by defining a new notion of what it means to approximate a graph by a sparser or smaller graph, and explain why these sparse approximations enable the fast solution of linear equations in diagonally-dominant matrices.

To build these sparsifiers, we rely on low-stretch spanning trees, random matrix theory, spectral graph theory, and graph partitioning algorithms.

The need to quickly partition a graph leads us to the local clustering problem: given a vertex in a massive graph, output a small cluster near that vertex in time proportional to the size of the cluster.

We use all these tools to design nearly-linear time algorithms for solving diagonally-dominant systems of linear equations, and give some applications.

This talk focuses on joint work with Shang-Hua Teng, and touches on work by Vaidya, Gremban, Miller, Koutis, Peng, Emek, Elkin, Andersen, Chung, Lang, Daitch, Srivastava and Batson.

Bio:

Daniel 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 of Applied Mathematics and Computer Science at Yale University.

The awards he has received include the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 Godel Prize and the 2009 Fulkerson Prize. In 2010, he was awarded the Nevanlinna Prize and was named a Fellow of the Association for Computing Machinery.

His main research interests include the design and analysis of algorithms, graph theory, machine learning, error-correcting codes and combinatorial scientific computing. www.cs.yale.edu/homes/spielman/

For event inquiries, please contact Chrissy Coleman. ccoleman@ttic.edu