Algorithms and Complexity Seminar
Twice-Ramanujan Sparsifiers
Nikhil Srivastava (Yale University)
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 in R^n,
x^T L_G x =< x^T L_H x =< (d+1+2sqrt(d) / d+1-2sqrt(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.