Hermann Weyl Lectures

Sparsification of graphs and matrices

Random graphs and expander graphs can be viewed as sparse approximations of complete graphs, with Ramanujan expanders providing the best possible approximations. We formalize this notion of approximation and ask how well an arbitrary graph can be approximated by a sparse graph. We prove that every graph can be approximated by a sparse graph almost as well as the complete graphs are approximated by the Ramanujan expanders: our approximations employ at most twice as many edges to achieve the same approximation factor. Our algorithms follow from the solution of a problem in linear algebra. Given an expression for 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. This is joint work with Joshua Batson, Nikhil Srivastava and Shang-Hua Teng.

Date & Time

November 03, 2014 | 2:00pm – 3:00pm

Location

S-101

Speakers

Daniel Spielman, Yale University

Affiliation

Yale University

Event Series

Categories