# Faster exact learning of k-term DNFs with membership and equivalence queries

arXiv: https://arxiv.org/abs/2507.20336 · HTML: https://mlsanity.com/paper/2507.20336/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2025.

## Built on by (most cited first, 1 of 1)

- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)

## Abstract (arXiv)

In 1992 Blum and Rudich [BR92] gave an algorithm that uses membership and equivalence queries to learn k-term DNF formulas over 0,1n in time textsfpoly(n,2k), improving on the naive O(nk) running time that can be achieved without membership queries [Val84]. Since then, many alternative algorithms [Bsh95, Kus97, Bsh97, BBB+00] have been given which also achieve runtime textsfpoly(n,2k). We give an algorithm that uses membership and equivalence queries to learn k-term DNF formulas in time textsfpoly(n) · 2^tildeO(√k). This is the first improvement for this problem since the original work of Blum and Rudich [BR92]. 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 [BR92] 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.