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).