David Bernstein, Martin C. Golumbic, et al.
ACM SIGPLAN Notices
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.
David Bernstein, Martin C. Golumbic, et al.
ACM SIGPLAN Notices
Nathan Linial, Yishay Mansour, et al.
FOCS 1989
Mihir Bellare
ACM COLT 1992
Israel Cidon, S. Kutten, et al.
SIAM Journal on Computing