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