Near-Linear Regimes for One-Sided Distribution-Free Junta Testing

Abstract

We study adaptive one-sided distribution-free testing of Boolean $k$-juntas, with membership-query access to the function and sample access to an arbitrary unknown distribution. For general Boolean functions, we give a tester using $O(k^2\log (k+1)+k/\epsilon )$ queries, independently of the ambient dimension. The tester maintains disjoint relevant blocks certified by observed disagreements. Within each fresh batch, it jointly decodes literal signatures for a small family of random base masks, then uses linear combinations to generate $\Theta (1/\epsilon )$ probes. Their ideal counterparts are pairwise independent, yielding constant conditional progress probability; a global $O(k)$ batch budget gives the additive query bound. Consequently, the complexity is $O((k/\epsilon )\log (k+1))$ when $\epsilon \le 1/k$, and $O(k/\epsilon )$ when $\epsilon \le 1/(k\log (k+1))$. We also analyze an indexed-table implementation that reuses previously computed block orientations. For functions symmetric on an unknown set of relevant variables, it uses $O(k{\log }^2(k+1)/\epsilon )$ queries: safely checked blocks contain a single globally relevant variable, making their cached nonliteral sides reusable. For arbitrary functions, a stable-deletion analysis establishes soundness of the same implementation at $O(k^2\log (k+1)/\epsilon )$ queries. All variants always accept $k$-juntas, and every rejection is certified by $k+1$ disjoint relevant blocks. The fresh-batch construction and the reuse analysis use the same certified-block framework, with different randomness and stopping rules.

References in corpus (1)

• Testing Unateness of Real-Valued Functions

Cited by in corpus (1)

• Junta Distance Approximation with Sub-Exponential Queries