Metraipolis › archive › dc_a28703fbc280
Fooling Thresholds of Halfspaces — arXiv:2609.21329
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.21329
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T02:51:55.140Z
- SHA-256 of the archived text
3c2d1bbbb84a373a2598e5bc27ea93b495198dd46e7206da4908327b8721e2ba- Stable URL of this page
https://metraipolis.com/documento/dc_a28703fbc280
How to cite
Fooling Thresholds of Halfspaces — arXiv:2609.21329 — arXiv (en), https://arxiv.org/abs/2609.21329 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a28703fbc280 (Metraipolis archive dc_a28703fbc280, sha256 3c2d1bbbb84a373a2598e5bc27ea93b495198dd46e7206da4908327b8721e2ba)
BibTeX
@misc{dca28703fbc280,
title = {Fooling Thresholds of Halfspaces — arXiv:2609.21329},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.21329},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a28703fbc280; sha256 3c2d1bbbb84a373a2598e5bc27ea93b495198dd46e7206da4908327b8721e2ba},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.21329. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We initiate the study of constructing explicit pseudorandom generators for thresholds of halfspaces with seed length polylogarithmic in the number of halfspaces. This class of functions lies at the frontier of circuit complexity [CTW26]. We show that the generator designed by O'Donnell, Servedio, and Tan for polytopes [OST22] also fools this broader class. To analyze the generator, we develop a threshold-specific smooth approximation framework based on a Bentkus-type mollifier. We prove derivative bounds for this mollifier and also establish a Boolean anticoncentration theorem for thresholds of halfspaces via a random thinning argument. These ingredients imply that the generator $\delta$-fools every $k$-out-of-$m$ threshold of $m$ halfspaces over $\{-1,1\}^n$ with seed length $\widetilde{O}(\kappa^{6+2\varepsilon}\log^{6+2\varepsilon}\!m\cdot\delta^{-(2+2\varepsilon)}\log n)$, for any arbitrarily small constant $\varepsilon>0$, where $\kappa=\min\{k,m-k+1\}$. The random thinning argument also yields bounds on the noise sensitivity and Gaussian surface area for thresholds of halfspaces, leading to learning algorithms under both the uniform and Gaussian distributions.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.21329 — 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-10T02:30:12.542Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).