Volume 5 (2009) Article 10 pp. 191-216
Distribution-Free Testing Lower Bound for Basic Boolean Functions
$\newcommand{\D}{{\cal D}}$
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.