Metraipolis › archive › dc_c97976bbde02
Distribution-Free Halfspace Testing with Samples — arXiv:2608.11346
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.11346
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T05:52:49.607Z
- SHA-256 of the archived text
5a472d1b8d0118f496a2634710f9e45faec3cbe42cbdd7059fdf0e5949953572- Stable URL of this page
https://metraipolis.com/documento/dc_c97976bbde02
How to cite
Distribution-Free Halfspace Testing with Samples — arXiv:2608.11346 — arXiv (en), https://arxiv.org/abs/2608.11346 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c97976bbde02 (Metraipolis archive dc_c97976bbde02, sha256 5a472d1b8d0118f496a2634710f9e45faec3cbe42cbdd7059fdf0e5949953572)
BibTeX
@misc{dcc97976bbde02,
title = {Distribution-Free Halfspace Testing with Samples — arXiv:2608.11346},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.11346},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c97976bbde02; sha256 5a472d1b8d0118f496a2634710f9e45faec3cbe42cbdd7059fdf0e5949953572},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.11346. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We prove a tight $\Theta(n/\epsilon)$ lower bound on the number of samples required for testing halfspaces over $\mathbb{R}^n$, in the distribution-free sample-based model where the underlying probability distribution is unknown to the algorithm, and the algorithm only receives random samples (i.e., it cannot make queries). This shows that testing is no more efficient than learning for halfspaces. We also show a matching upper bound for one-sided testers, improving on the standard (two-sided) testing-by-learning reduction, establishing that two-sided halfspace testers in this model have no advantage over one-sided testers.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-13 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.11346 — 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-19T05:48:37.113Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).