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.