[Colloquium] TTIC Distinguished Lecture- March 7 DANIEL SPIELMAN, Yale University.

[Chrissy Novak]

Good afternoon,

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 Gödel 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 Novak. cnovak at ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20110223/78144960/attachment.htm