Sparsifying Cayley Graphs on Every Group

A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a (1 ± ε) cut (or spectral) sparsifier which preserves only O(n/ε 2 ) reweighted edges. However, when applying this result to Cayley graphs, the resulting sparsifier is no longer necessarily a Cayley graph -it can be an arbitrary subset of edges.

Thus, a recent line of inquiry, and one which has only seen minor progress, asks: for any group G, do all Cayley graphs over the group G admit sparsifiers which preserve only polylog(|G|)/ε 2 many re-weighted generators?

As our primary contribution, we answer this question in the affirmative, presenting a proof of the existence of such Cayley graph spectral sparsifiers, along with an efficient algorithm for finding them. Our algorithm even extends to directed Cayley graphs, if we instead ask only for cut sparsification instead of spectral sparsification.

We additionally study the sparsification of linear equations over non-abelian groups. In contrast to the abelian case, we show that for non-abelian valued equations, super-polynomially many linear equations must be preserved in order to approximately preserve the number of satisfied equations for any input. Together with our Cayley graph sparsification result, this provides a formal separation between Cayley graph sparsification and sparsifying linear equations.