An O(n^(log log n)) Learning Algorithm for DNT under the Uniform Distribution
We show that a DNF with terms of size at most d can be approximated by a function with at most d O(d log1=") non zero Fourier coeecients 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 d O(dlog 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 n O(loglog n) , and a DNF with terms of size at most O(log n= log log n) in polynomial time.