## Twice-Ramanujan Sparsifiers

by Joshua D. Batson and Daniel A. Spielman and Nikhil Srivastava

We prove that for every $d>1$ and every undirected, weighted graph $G(V,E)$ on $n$ vertices, there exists a weighted subgraph $H$ of $G$ with at most $dn$ edges that preserves the Laplacian quadratic form of $G$ up to a multiplicative error of $1\pm 4\sqrt{1/d}$. 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$.