Distribution-Free Testing Lower Bounds for Basic Boolean Functions.
D. Glasner and R. Servedio.
Theory of Computing, 5(1), 2009, pp. 191-216.
Preliminary version in 11th International Workshop on Randomness and Computation (RANDOM), 2007, pp. 494--508.


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 learnable (and hence testable) using Theta(n) oracle calls, our lower bounds are within a polynomial factor of the best possible.

pdf of full version of conference paper

Link to open-access journal version

Back to main papers page