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.