Published: September 8, 2011

**Keywords:**property testing, distribution-free testing, Boolean functions, monomials

**Categories:**complexity theory, decision tree, property testing, distribution-free testing, Boolean functions, conjunction

**ACM Classification:**F.2.2, G.2.0, G.3

**AMS Classification:**68Q25, 68W20, 68W40

**Abstract:**
[Plain Text Version]

We consider the problem of distribution-free testing
of the class of monotone monomials and the class of monomials
over $n$ variables.
While there are very efficient testers for a variety
of classes of functions
when the underlying distribution is uniform,
designing distribution-free testers (which must work under
an arbitrary and unknown distribution) tends to be more challenging.
When the underlying distribution is uniform,
Parnas et al. (*SIAM J. Discr. Math., 2002*)
give a tester for (monotone) monomials whose query complexity
does not depend on $n$, and whose dependence on the distance
parameter is (inverse) linear.
In contrast, Glasner and Servedio
(*Theory of Computing, 2009*)
prove that every
distribution-free tester for monotone monomials as
well as for general monomials must have query
complexity $\widetilde{\Omega}(n^{1/5})$ (for a constant
distance parameter $\epsilon$).

In this paper we present distribution-free testers for these classes whith query complexity $\widetilde{O}(n^{1/2}/\epsilon)$. We note that in contrast to previous results for distribution-free testing, our testers do not build on the testers that work under the uniform distribution. Rather, we define and exploit certain structural properties of monomials (and functions that differ from them on a non-negligible part of the input space), which were not used in previous work on property testing.