Faster Exact Learning of k-Term DNFs with Membership and Equivalence Queries

In 1992 Blum and Rudich [1] gave an algorithm that uses membership and equivalence queries to learn k-term DNF formulas over $\{0,1\}^{n}$ in time $\operatorname{poly}\left(n, 2^{k}\right)$, improving on the naive $O\left(n^{k}\right)$ running time that can be achieved without membership queries [2]. Since then, many alternative algorithms [3]–[6] have been given which also achieve runtime poly $\left(n, 2^{k}\right)$. We give an algorithm that uses membership and equivalence queries to learn k-term DNF formulas in time poly $(n) \cdot 2^{\tilde{O}(\sqrt{k})}$. This is the first improvement for this problem since the original work of Blum and Rudich [1]. Our approach employs the Winnow2 algorithm for learning linear threshold functions over an enhanced feature space which is adaptively constructed using membership queries. It combines a strengthened version of a technique that effectively reduces the length of DNF terms from the original work of [1] with a range of additional algorithmic tools (attribute-efficient learning algorithms for low-weight linear threshold functions and techniques for finding relevant variables from junta testing) and analytic ingredients (extremal polynomials and noise operators) that are novel in the context of query-based DNF learning.