An O(n log log n ) learning algorithm for DNF under the uniform distribution
Yishay Mansour · 1992
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.