Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Volume 5 (2009) Article 10 pp. 191-216
Distribution-Free Testing Lower Bound for Basic Boolean Functions
Received: September 18, 2008
Published: October 17, 2009
Download article from ToC site:
[PDF (378K)] [PS (1311K)] [Source ZIP]
Keywords: property testing, distribution-free testing, decision list, conjunction, linear threshold function
ACM Classification: F.2.2, G.3
AMS Classification: 68Q99, 69W20

Abstract: [Plain Text Version]

\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.