Published: October 17, 2009

**Keywords:**property testing, distribution-free testing, decision list, conjunction, linear threshold function

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

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

**AMS Classification:**68Q99, 69W20

**Abstract:**
[Plain Text Version]

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.