# On Exact Learning Monotone DNF from Membership Queries

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2014.

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

- [Learning Low Degree Hypergraphs](https://mlsanity.com/paper/2202.09989/) (2022)
- [Non-adaptive Learning of Random Hypergraphs with Queries](https://mlsanity.com/paper/2501.12771/) (2025)
- [Formal Models of Active Learning from Contrastive Examples](https://mlsanity.com/paper/2506.15893/) (2025)
- [Local-to-Global Logical Explanations for Deep Vision Models](https://mlsanity.com/paper/2601.13404/) (2026)
- [Symphony in the Latent Space: Provably Integrating High-dimensional Techniques with Non-linear Machine Learning Models](https://mlsanity.com/paper/2212.00852/) (2022)
- [Adaptive Sparse M"obius Transforms for Learning Polynomials](https://mlsanity.com/paper/2602.06246/) (2026)

## Abstract (arXiv)

In this paper, we study the problem of learning a monotone DNF with at most s terms of size (number of variables in each term) at most r (s term r-MDNF) from membership queries. This problem is equivalent to the problem of learning a general hypergraph using hyperedge-detecting queries, a problem motivated by applications arising in chemical reactions and genome sequencing. We first present new lower bounds for this problem and then present deterministic and randomized adaptive algorithms with query complexities that are almost optimal. All the algorithms we present in this paper run in time linear in the query complexity and the number of variables n. In addition, all of the algorithms we present in this paper are asymptotically tight for fixed r and/or s.