Metraipolis › archive › dc_3f2eddd4f16d
Ranked spreadness and sample-based testing — arXiv:2608.03758
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.03758
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T12:54:00.064Z
- SHA-256 of the archived text
ccf175b7d07fc4f391ccfc352a2dda2bcc962cc11ad4e4ce4f3d78224239bb39- Stable URL of this page
https://metraipolis.com/documento/dc_3f2eddd4f16d
How to cite
Ranked spreadness and sample-based testing — arXiv:2608.03758 — arXiv (en), https://arxiv.org/abs/2608.03758 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3f2eddd4f16d (Metraipolis archive dc_3f2eddd4f16d, sha256 ccf175b7d07fc4f391ccfc352a2dda2bcc962cc11ad4e4ce4f3d78224239bb39)
BibTeX
@misc{dc3f2eddd4f16d,
title = {Ranked spreadness and sample-based testing — arXiv:2608.03758},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.03758},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3f2eddd4f16d; sha256 ccf175b7d07fc4f391ccfc352a2dda2bcc962cc11ad4e4ce4f3d78224239bb39},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.03758. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In this note, we introduce the notion of ranked spreadness, a strengthening of the usual spread condition in which the elements of each member can be ordered so that their one-coordinate marginals decay geometrically with their rank. This additional structure removes the dependence on the maximum set size in random-containment estimates. We prove width-free hitting and weighted-concentration theorems for ranked-spread set systems, together with an elementary kernel-extraction theorem showing that ranked spreadness arises naturally in arbitrary distributions on small sets. Our main application is to the simulation of nonadaptive property testers by sample-based testers. If a one-sided tester has average query complexity $d$ and rejects every far input with probability at least $\delta$, then, for every integer $c>d/\delta$, it admits a one-sided sample-based simulation with expected sample complexity $O_{d,\delta,|\Sigma|}\bigl(n^{1-1/c}\bigr)$. More generally, if positive inputs are rejected with probability at most $\gamma$ and far inputs with probability at least $\delta>\gamma$, the same conclusion holds for every $c>d/(\delta-\gamma)$. In particular, for constant-query nonadaptive testers we obtain an exponent $1-\Theta(1/q)$, matching, up to the dependence on the rejection gap, the exponent conjectured by Fischer, Lachish, and Vasudev.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-05 in math.ST).
Categorie arXiv: Statistics Theory (math.ST) ; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.03758 — 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-31T12:41:37.331Z dalla pagina https://arxiv.org/catchup/math.ST/2026-08-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).