This is a set of notes for a paper from the learning theory reading group, which I’m posting here with some keywords so I can easily search for them. I doubt they’ll be useful for anyone else, but who knows?
These notes include notes on the following material which is a pre-requisite for understanding this paper:
Kushilevitz and Mansour First gave a polynomial time membership query algorithm for learning decision trees under the uniform distribution. Their algorithm uses a subroutine (often called KM), based on the list-decoding algorithm of Goldreich and Levin, which fnds and estimates all “large” Fourier coefficients of the target function using membership queries. Subsequently Jackson extended the KM algorithm and combined it with the hypothesis boosting algorithm of Freund to give the Harmonic Sieve algorithm, which uses membership queries to learn DNF under the uniform distribution in polynomial time. Bshouty and Feldman later observed that a certain algorithmic variant of KM, which they called the Bounded Sieve, is all that is necessary for Jackson’s algorithm to work.
Dr. O’Donnel has some slides from a DNF survey talk here