Ranked spreadness and sample-based testing

Abstract

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 |}\left(n^{1-1/c}\right)$. 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.

Comments are welcome!