We prove a new structural lemma for partial Boolean functions $f$, which we call the {\em seed lemma for DNF}. Using the lemma, we give the first subexponential algorithm for proper learning of poly$(n)$-term DNF in Angluin's Equivalence Query (EQ) model. The algorithm has time and query complexity $2^{(\tilde{O}{\sqrt{n}})}$, which is optimal. We also give a new result on certificates for DNF-size, a simple algorithm for properly PAC-learning DNF, and new results on EQ-learning $\log n$-term DNF and decision trees.
Link to open-access JMLR Workshop & Conference Proceedings version