{"ID":6267109,"CreatedAt":"2026-07-10T01:11:38.759438437Z","UpdatedAt":"2026-07-13T01:02:08.706470581Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.08261","arxiv_id":"2607.08261","title":"Optimal Sparsifiers for Abelian Cayley Graphs","abstract":"We prove that for every Cayley graph $\\mathcal{G}$ over any finite abelian group $G$, there is a weighted Cayley graph with $O(\\log |G|)$ generators that is a spectral sparsifier for $\\mathcal{G}$. This bound is optimal. Applying our bound to the group $G = \\mathbb{F}_2^n$, yields, as a corollary, $O(n/\\varepsilon^2)$-sized code sparsifiers for $\\mathbb{F}_2$-linear codes, improving on the work of Khanna, Putterman and Sudan (SODA'24) who obtained a similar result with an additional $\\mathrm{polylog}(n)$ loss. Our proof is strongly inspired by a recent work of Reis and Rothvoss for the construction of $\\ell_1$-sparsifiers. Following their work, the abelian Cayley sparsification problem can be reduced to establishing a lower bound for the volume of a certain natural convex body. This volume bound follows from a short, elementary argument that relies on character symmetry.","short_abstract":"We prove that for every Cayley graph $\\mathcal{G}$ over any finite abelian group $G$, there is a weighted Cayley graph with $O(\\log |G|)$ generators that is a spectral sparsifier for $\\mathcal{G}$. This bound is optimal. Applying our bound to the group $G = \\mathbb{F}_2^n$, yields, as a corollary, $O(n/\\varepsilon^2)$-...","url_abs":"https://arxiv.org/abs/2607.08261","url_pdf":"https://arxiv.org/pdf/2607.08261v1","authors":"[\"Arpon Basu\",\"Pravesh K. Kothari\",\"Raghu Meka\",\"Stefan Tudose\"]","published":"2026-07-09T09:05:00Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}