Theory of Computing
-------------------
Title : Distribution-Free Testing Lower Bound for Basic Boolean Functions
Authors : Dana Glasner and Rocco A. Servedio
Volume : 5
Number : 10
Pages : 191-216
URL : https://theoryofcomputing.org/articles/v005a010
Abstract
--------
In the "distribution-free" property testing model, the distance
between functions is measured with respect to an arbitrary and
unknown probability distribution D over the input domain. We
consider distribution-free testing of several basic Boolean function
classes over {0,1}^n, namely monotone conjunctions, general
conjunctions, decision lists, and linear threshold functions.
We prove that for each of these function classes,
Omega((n / log n)^{1/5} oracle calls are required for any
distribution-free testing algorithm. Since each of these function
classes is known to be distribution-free properly learnable (and
hence testable) using Theta(n) oracle calls, our lower bounds
are polynomially related to the best possible.