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