@inbook {19567,
	title = {Distribution-Free Testing Lower Bounds for Basic Boolean Functions},
	booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
	series = {Lecture Notes in Computer Science},
	year = {2007},
	month = {2007/01/01/},
	pages = {494 - 508},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	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.},
	keywords = {Algorithm Analysis and Problem Complexity, Discrete Mathematics in Computer Science, Numeric Computing},
	isbn = {978-3-540-74207-4, 978-3-540-74208-1},
	url = {http://link.springer.com/chapter/10.1007/978-3-540-74208-1_36},
	author = {Dana Dachman-Soled and Servedio, Rocco A.},
	editor = {Charikar, Moses and Jansen, Klaus and Reingold, Omer and Rolim, Jos{\'e} D. P.}
}
