Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPs
Swap coboundary expansion, introduced independently by Bafna--Minzer and Dikstein--Dinur, is a local-to-global property that underlies agreement tests in the low-acceptance regime and recent constructions of succinct PCPs. Previous works obtained bounds of $\exp(-O(\sqrt{r}))$ for the $r$-swap coboundary expansion of Chapman--Lubotzky complexes. We establish the first inverse-polynomial bounds for bounded-degree complexes: suitable skeleta of Kac--Moody--Steinberg (KMS) complexes have $r$-swap coboundary expansion at least $r^{-O(1)}$. Our theorem supplies a key ingredient in forthcoming work of Ben Yaacov--Dikstein--Liu, which obtains local tests for sparse algebraic codes with guarantees even at arbitrarily small acceptance probability. These tests use $\exp(\operatorname{poly}(1/\varepsilon))$ queries and guarantee that any word accepted with probability at least $\varepsilon$ agrees with a codeword on an $\varepsilon^{O(1)}$ fraction of coordinates. Separately, substituting our bound into the existing analysis of Bafna--Minzer--Vyas--Yun improves the soundness dependence of their two-query PCP construction, giving perfect completeness, soundness $\varepsilon$, and proof length $n(\log n)^{\exp(\operatorname{poly}(1/\varepsilon))}$. Our proof exploits the product structure of the groups arising in KMS complexes. The main new ingredient is a decomposition lemma for Dehn functions, which separates the analysis of group relations into independent problems on much smaller factors, with only polynomial overhead.
Authors
- Yotam Dikstein (ORCID: https://orcid.org/0000-0002-6248-6574)
- Izhar Oppenheim (ORCID: https://orcid.org/0000-0002-1849-1851)
- Inga Valentiner-Branth (ORCID: https://orcid.org/0000-0001-7744-8733)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.48550/arxiv.2611.16295
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint