# Distribution-Free Testing Lower Bounds for Basic Boolean Functions

 Title Distribution-Free Testing Lower Bounds for Basic Boolean Functions Publication Type Book Chapters Year of Publication 2007 Authors Dachman-Soled D, Servedio RA Editor Charikar M, Jansen K, Reingold O, Rolim JDP Book Title Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques Series Title Lecture Notes in Computer Science Pagination 494 - 508 Publisher Springer Berlin Heidelberg ISBN Number 978-3-540-74207-4, 978-3-540-74208-1 Keywords Algorithm Analysis and Problem Complexity, Discrete Mathematics in Computer Science, Numeric Computing Abstract 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. URL http://link.springer.com/chapter/10.1007/978-3-540-74208-1_36