Fast learning of k -term DNF formulas with queries
Avrim L. Blum, Steven Rudich · 1992
This paper presents an algorithm that uses equivalence and membership queries to learn the class of k-term DNF formulas in time O(n•2o(k)), where n is the number of input variables. This improves upon previous O(nk) bounds and allows one to learn DNF of O(log n) terms in polynomial time. We present the algorithm in its most natural form as a randomized algorithm, and then show how recent derandomization techniques can be used to make it deterministic. The algorithm is an exact learning algorithm, but one where the equivalance query hypotheses and the final output are general (not necessarily k-term) DNF formulas.