Twice-Ramanujan Sparsifiers

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,˜w) with at most dn edges such that for every

x ∈ RV,
xT LG x ≤ xT LH x ≤ ( d+1+2√d / d+1-2√d ) xT LG x

where LG and LH 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.

发言人详细信息

Nikhil is a 5th year graduate student at Yale, studying spectral graph theory and linear algebra with Dan Spielman. He interned with MSR twice: in Bangalore in 2008 and at SVC in 2009. He graduated from Union College in 2005 with a BS in Math, CS, and English.

日期：
演讲者：
Nikhil Srivastava
所属机构：
Yale