
Speaker Nikhil Srivastava Host Jennifer Chayes Affiliation Yale Duration 01:09:55 Date recorded 15 January 2010 We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linearsized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every d > 1 and every undirected, weighted graph G = (V,E,w) on n vertices, there exists a weighted graph H=(V,F,˜w) with at most dn edges such that for every x ∈ R^{V}, where L_{G} and L_{H} are the Laplacian matrices of G and H, respectively. Thus, H approximates G spectrally at least as well as a Ramanujan expander with dn/2 edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing H. Joint work with Josh Batson and Dan Spielman.
©2010 Microsoft Corporation. All rights reserved.
