Twice-Ramanujan Sparsifiers

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

Oded's comments

A special case of this result refers to the construction of a cut sparsifiers which is a subgraph that preserves the relative densities of all cuts in the original graph. However, the generalization offers verifiability (since the approximation of eigenvalues offers by the sparsifier can be easily determined).

The paper presents a (deterministic) polynomial-time algorithm that finds such a sparsifier with a linear number of edges, improving over prior works that obtained an almost linear number of edges via a probabilistic polynomial-time algorithm. The odd title refers to the fact that the degree bound achieved here is twice the one obtained for the special case of the complete graph. Unfortunately, this is not the only oddity in the exposition.

See related talk by Dan Spielman.

The original abstract

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$.

Back to list of Oded's choices.