%0 Book Section
%B Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
%D 2007
%T Distribution-Free Testing Lower Bounds for Basic Boolean Functions
%A Dana Dachman-Soled
%A Servedio, Rocco A.
%E Charikar, Moses
%E Jansen, Klaus
%E Reingold, Omer
%E Rolim, José D. P.
%K Algorithm Analysis and Problem Complexity
%K Discrete Mathematics in Computer Science
%K Numeric Computing
%X In the distribution-free property testing model, the distance between functions is measured with respect to an arbitrary and unknown probability distribution \mathcal{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, Ω((n/logn)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 Θ(n) oracle calls, our lower bounds are within a polynomial factor of the best possible.
%B Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
%S Lecture Notes in Computer Science
%I Springer Berlin Heidelberg
%P 494 - 508
%8 2007/01/01/
%@ 978-3-540-74207-4, 978-3-540-74208-1
%G eng
%U http://link.springer.com/chapter/10.1007/978-3-540-74208-1_36