Weakly learning DNF and characterizing statistical query learning using Fourier analysis

Abstract

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