Skip to content
DraconiticResearch
Search Sources API
190,851 studies31 sourcesUpdated 18 min ago
PreprintCC BY-SA 4.0arXiv

Optimal Sparsifiers for Abelian Cayley Graphs

  • Arpon Basu
  • Pravesh K. Kothari
  • Raghu Meka
  • Stefan Tudose
Open at sourcePDFDOICite

Abstract

We prove that for every Cayley graph 𝒒 over any finite abelian group G, there is a weighted Cayley graph with O(log |G|) generators that is a spectral sparsifier for 𝒒. This bound is optimal. Applying our bound to the group G = 𝔽2n, yields, as a corollary, O(n/Ξ΅2)-sized code sparsifiers for 𝔽2-linear codes, improving on the work of Khanna, Putterman and Sudan (SODA'24) who obtained a similar result with an additional polylog(n) loss. Our proof is strongly inspired by a recent work of Reis and Rothvoss for the construction of β„“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.

Related

  1. Cayley graphs of abelian groups, circular colorings and discrete fundamental groups
    Kengo Enami, Takahiro Matsushita
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. Fast robbers on abelian Cayley graphs and digraphs
    Arindam Biswas
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Isomorphisms of abelian Cayley graphs with their natural edge-colouring
    Shirin Alimirzaei, Dave Witte Morris
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Exact Diameter Windows for Random Cayley Graphs on Odd-Order Abelian Groups
    Yao Zhi
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  5. A complete classification of perfect state transfer in Grover walks on abelian Cayley graphs
    Koushik Bhakta, Bikash Bhattacharjya
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{basu2026optimal,
  title = {{Optimal Sparsifiers for Abelian Cayley Graphs}},
  author = {Arpon Basu and Pravesh K. Kothari and Raghu Meka and Stefan Tudose},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2607.08261},
  eprint = {2607.08261},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.08261},
  note = {CC BY-SA 4.0},
}
RIS
TY  - UNPB
TI  - Optimal Sparsifiers for Abelian Cayley Graphs
AU  - Arpon Basu
AU  - Pravesh K. Kothari
AU  - Raghu Meka
AU  - Stefan Tudose
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2607.08261
UR  - https://arxiv.org/abs/2607.08261
AB  - We prove that for every Cayley graph 𝒒 over any finite abelian group G, there is a weighted Cayley graph with O(log |G|) generators that is a spectral sparsifier for 𝒒. This bound is optimal. Applying our bound to the group G = 𝔽_2^n, yields, as a corollary, O(n/Ξ΅^2)-sized code sparsifiers for 𝔽_2-linear codes, improving on the work of Khanna, Putterman and Sudan (SODA'24) who obtained a similar result with an additional polylog(n) loss. Our proof is strongly inspired by a recent work of Reis and Rothvoss for the construction of β„“_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.
ER  -