Twice-Ramanujan Sparsifiers

165 views · Published 18 August 2016 · 1:10:19 · Indexed 8 November 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized 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,\tilde{w}) with at most dn edges such that for every    x \in \R^{V},  x^T L_G x \leq x^T L_H x        \leq ( d+1+2\sqrt{d} / d+1-2\sqrt{d} ) x^T L_G x     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.

More from this channel