Optimal Sparsifiers for Abelian Cayley Graphs
Provides optimal sparsifiers for abelian Cayley graphs, with implications for coding theory, improving known bounds for linear code sparsifiers.
The authors prove that every Cayley graph over a finite abelian group has a spectral sparsifier with O(log |G|) generators, which is optimal. This yields O(n/ε^2)-sized code sparsifiers for F2-linear codes, improving on prior work by removing a polylog(n) factor.
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.