The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


             Walmart Lecture Series in Cryptography and Complexity

                     Lecture Hall, Room 1, Ziskind Building
                            on Sunday, May 15, 2011
                                    at 11:00





                                Daniel Spielman
                                Yale University


                                 will speak on


        Spectral Sparsification of Graphs and Approximations of Matrices

Abstract:
Expander graphs can be viewed as sparse approximations of complete graphs, with
Ramanujan expanders providing the best possible approximation.

We formalize this notion of approximation and ask how well a given 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.

We also present an efficient randomized algorithm for constructing sparse
approximations that 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.

This is joint work with Joshua Batson, Nikhil Srivastava and Shang-Hua Teng.