{"ID":2883804,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.08078","arxiv_id":"2508.08078","title":"Sparsifying Cayley Graphs on Every Group","abstract":"A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a $(1 \\pm \\varepsilon)$ cut (or spectral) sparsifier which preserves only $O(n / \\varepsilon^2)$ reweighted edges. However, when applying this result to \\emph{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 $\\mathrm{polylog}(|G|)/\\varepsilon^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 \\emph{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.","short_abstract":"A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a $(1 \\pm \\varepsilon)$ cut (or spectral) sparsifier which preserves only $O(n / \\varepsilon^2)$ reweighted edges. However, when applying this result to \\emph{Cayley graphs}, the resulting sparsifier is n...","url_abs":"https://arxiv.org/abs/2508.08078","url_pdf":"https://arxiv.org/pdf/2508.08078v1","authors":"[\"Jun-Ting Hsieh\",\"Daniel Z. Lee\",\"Sidhanth Mohanty\",\"Aaron Putterman\",\"Rachel Yun Zhang\"]","published":"2025-08-11T15:25:06Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}