
Speaker Dan Alan Spielman Affiliation Yale Duration 01:17:03 Date recorded 28 July 2010 We introduce a notion of what it means for one graph to be a good spectral approximation of another. This induces the problem of spectral sparsification: finding a sparse graph that is a good spectral approximation of a given graph. It turns out that Ramanujan expanders are the best sparse spectral approximations of complete graphs. We show that every graph may be approximated almost as well by a sparse graph as the complete graphs are by Ramanujan graphs. We also present an efficient randomized algorithm for construction 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 a rankn symmetric matrix A that is expressed as a sum of rank1 symmetric matrices, we show that A can be well approximated by a weighted sum of only O(n) of those rank1 matrices. This is joint work with Joshua Batson, Nikhil Srivastava and ShangHua Teng.
©2010 Microsoft Corporation. All rights reserved.
