Tight Bounds on Proper Equivalence Query Learning of DNF

Lisa Hellerstein, Devorah Kletenik, Linda Sellie +1

We prove a new structural lemma for partial Boolean functions $f$, which we call the seed lemma for DNF. Using the lemma, we give the first subexponential algorithm for proper lear…