On using the Fourier transform to learn disjoint DNF (Q1318745)

This paper addresses the problem of learning DNF expressions using membership queries. We extend previous results by \textit{E. Kushilevitz} and \textit{Y. Mansour} [SIAM J. Comput. 22, No. 6, 1331-1348 (1993)], on learning through Fourier representations, to show learnability of various subsets of DNF. In particular we show the polynomial learnability of disjoint DNF expressions under the uniform distribution, and exact learnability of disjoint \(\log n\) DNF. Disjoint DNF expressions are DNF expressions (disjunctions of conjunctions) in which every truth assignment satisfies at most one term. In disjoint \(\log n\) DNF expressions every conjunct is of length at most \(\log n\). We further show the learnability of \(\log n\) term DNF under the uniform distribution. The learnability of this class is already known but the algorithm and analysis given here are different. The learning algorithm we use is the one given by Kushilevitz and Mansour. The main contribution of this note is a different analysis of the Fourier spectrum of the respective function classes. This enables us to show the learnability of wider classes and with somewhat simplified proofs.