[Colloquium] [CS] THEORY SEMINAR TALK TODAY: Daniel Spielman

[Donna Brooms]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO - THEORY SEMINAR

Date: Tuesday, March 8, 2011
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

________________________________________

Speaker:  Daniel Spielman

From:  Yale University

Web page:  http://www.cs.yale.edu/homes/spielman

Title: Title: Spectral Sparsification of Graphs and Approximations of Matrices
 

Abstract:  We introduce a notion of what it means for one graph to be a good spectral approximation of another. This leads us to ask how well a given graph can be approximated by a sparse graph.                                                                               

It turns out that Ramanujan expanders are the best sparse spectral approximations of complete graphs. We prove that every graph can be approximated almost as well by a sparse graph as the complete graphs are by Ramanujan expanders. We also present an efficient randomized algorithm for constructing sparse approximations which only uses a logarithmic factor more edges than optimal.                                                                                       

Our algorithms follow from the solution of a problem in linear algebra. Given any expression of a rank-n symmetric matrix A as a sum of rank-1 symmetric matrices, we show that A can be well approximated by a weighted sum of only O(n) of those rank-1 matrices.

Joint work with TTIC _____________________________________________________________________

Host: Prof. Alexander Razborov 

Refreshments will be served prior to the talk at 2:30 in Ryerson 255  

                                                                                           

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20110308/72f23b95/attachment.htm