Metraipolis › archive › dc_0411902bbb0d
Sumset Structure in Local Computation — arXiv:2609.22732
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.22732
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T22:41:19.718Z
- SHA-256 of the archived text
7b8f6213bd8f1f5385e47e69a0eb9b5caad2c58c26ef96f1cc9901cc48f3ce65- Stable URL of this page
https://metraipolis.com/documento/dc_0411902bbb0d
How to cite
Sumset Structure in Local Computation — arXiv:2609.22732 — arXiv (en), https://arxiv.org/abs/2609.22732 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0411902bbb0d (Metraipolis archive dc_0411902bbb0d, sha256 7b8f6213bd8f1f5385e47e69a0eb9b5caad2c58c26ef96f1cc9901cc48f3ce65)
BibTeX
@misc{dc0411902bbb0d,
title = {Sumset Structure in Local Computation — arXiv:2609.22732},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.22732},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0411902bbb0d; sha256 7b8f6213bd8f1f5385e47e69a0eb9b5caad2c58c26ef96f1cc9901cc48f3ce65},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.22732. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each internal node queries an $\ell$-local function of the input. We show that sufficiently strong lower bounds for $\ell$-local decision trees would imply several breakthrough circuit lower bounds, including super-linear size lower bounds for log-depth circuits and improved bounds for unrestricted-depth circuits. Previously, such consequences were known to follow from strong lower bounds for depth-$3$ circuits, which has been the main prior approach in attempting to prove these results. Since local decision trees are strictly weaker than depth-$3$ circuits, this provides a formally easier route to the same circuit lower-bound consequences. We prove essentially optimal lower bounds for a weaker variant that we call oblivious $\ell$-local decision trees, where all nodes at the same depth query the same function. Our lower bounds follow from a new technique that uncovers sumset structure in local maps, and our hard functions are sumset dispersers, sumset condensers, and directional affine dispersers. Along the way, we give an explicit construction of a sumset condenser with small entropy loss. As an additional contribution, we initiate the study of degree-$2$ decision trees, in which each query is a quadratic polynomial of the input. We show that proving lower bounds in this model is a natural stepping stone toward constructing dispersers for degree-$2$ variety sources, which imply improved circuit lower bounds for unrestricted depth circuits. We prove nearly maximal lower bounds for the oblivious variant of the model. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in cs.CC). Categorie arXiv: Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2609.22732 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-09T22:24:34.146Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).