A spectral sparsifier of a graph G is a weighted graph H on the same set of vertices such that the quadratic forms of the Laplacians of G and H are within a (1+eps) factor of each other. It is known by work of Batson et al. that every graph on n vertices admits a spectral sparsifier with average degree approximately 32/epsilon^2, and that it is not possible to do better than 4/eps^2. I will discuss two results which sharpen our understanding of the approximation-sparsity tradeoff.

(1) Any spectral sparsifier must in fact have average degree 16/eps^2. The proof is based on a new Alon-Boppana type bound for irregular weighted graphs with high girth.
(2) Any data structure (not necessarily a graph) which stores the sizes of all cuts in a graph up to error (1+eps) must use at least Omega(n\log n/eps^2) bits, so it is not possible to compress the cut structure of a graph using asymptotically fewer bits than a spectral sparsifier. This follows from a "rigidity" phenomenon: any two d-regular graphs which (1+c/sqrt(d))-approximate each other's cuts for sufficiently small c must in fact have a constant fraction of edges in common.

Based on joint work with Charles Carlson, Alexandra Kolla, and Luca Trevisan.