Paperlane

no. 14 · Friday 13 November 2026

Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPs

Yotam Dikstein, Izhar Oppenheim and Inga Valentiner-Branth

math.CO · 63 pp

Abstract

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.

comments
63 pages
fields
Combinatorics, Group Theory
pdf ↗ page arXiv:2611.16295 ↗