Theory of Computing
-------------------
Title : Distribution-Free Testing for Monomials with a Sublinear Number of Queries
Authors : Elya Dolev and Dana Ron
Volume : 7
Number : 11
Pages : 155-176
URL : http://www.theoryofcomputing.org/articles/v007a011
Abstract
--------
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 Omega~(n^{1/5}) (for a constant
distance parameter epsilon).
In this paper we present distribution-free testers for these
classes whith query complexity 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.