Weakly learning DNF and characterizing statistical query learning using Fourier analysis

Authors: Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, Steven Rudich - ACM Symposium on Theory of Computing, STOC 1994 cited by 264

We present new results, both positive and negative, on the well-studied problem of learning disjunctive normal form (DNF) expressions. We first prove that an algorithm due to Kushilevitz and Mansour ysis of a finite class of boolean functions 011 the hypercube. 1