Learning DNF by Statistical and Proper Distance Queries Under the Uniform Distribution Author: Wolfgang Lindner Source: Algorithmic Learning Theory, 16th International Conference, ALT 2005, Singapore, October 2005, Proceedings, (Sanjay Jain, Hans Ulrich Simon and Etsuji Tomita, Eds.), Lecture Notes in Artificial Intelligence 3734, pp. 198 - 210, Springer 2005. Abstract. We show that s-term DNF formulas can be learned under the uniform distribution in quasi-polynomial time with statistical queries of tolerance Ω(&epsilon/s). The tolerance improves on the known tolerance Ω(&epsilon2/s) and is optimal with respect to its dependence on the error parameter &epsilon. We further consider the related model of learning with proper distance queries and show that DNF formulas can be learned under the uniform distribution with quasi-polynomial queries, where the hypotheses are DNF formulas of polynomial size. Finally we consider the class of majorities over DNF formulas and provide polynomially related upper and lower bounds for the number of distance queries required to learn this class. ©Copyright 2005, Springer