Weakly learning DNF and characterizing statistical query learning using Fourier analysis
Avrim L. Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, Steven Rudich · 1994
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