In his seminal work, Valiant defined algebraic analogs for the classes P and NP, which are known today as VP and VNP. He also showed that the permanent is VNP-complete (that is, the permanent is in VNP and any problem in VNP is reducible to it). We will describe the ideas behind the proof of this completeness of the permanent.
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 ∈ ℜV ,