About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ACM COLT 1992
Conference paper
O(nlog log n) learning algorithm for DNF under the uniform distribution
Abstract
We show that a DNF with terms of size at most d can be approximated by a function with at most dO(d log 1/ε) non zero Fourier coefficients such that the expected error squared, with respect to the uniform distribution, is at most ε. This property is used to derive a learning algorithm for DNF, under the uniform distribution. The learning algorithm uses queries and learns, with respect to the uniform distribution, a DNF with terms of size at most d in time polynomial in n and dO(d log 1/ε). The interesting implications are for the case when ε is constant. In this case our algorithm learns a DNF with a polynomial number of terms in time nO(log log n), and a DNF with terms of size at most O(log n/log log n) in polynomial time.