Polynomial-time DNF learning from uniform random examples
For positive integers $n$ and $s$, let $\mathcal{D}_{n,s}$ be the class of Boolean functions on $\{0,1\}^n$ computed by a DNF formula with at most $s$ terms, with no restriction on the lengths, overlaps or signs of the terms. A learner for $\mathcal{D}_{n,s}$ is a classical randomized algorithm that is given $n$, $s$, $\varepsilon$, $\delta$ and independent labelled examples $(X, f(X))$ with $X$ uniform on $\{0,1\}^n$, and no other access to the unknown $f$: no membership queries and no quantum examples. It outputs a description of a hypothesis $h\colon \{0,1\}^n \to \{0,1\}$, not necessarily a DNF formula; its running time includes reading the examples, and $h$ must be evaluable in time polynomial in the same parameters as the running time. Verbeurgt gave an algorithm that learns $\mathcal{D}_{n,s}$ from uniform random examples alone in time $n^{O(\log(s/\varepsilon))}$. With membership queries, Jackson's Harmonic Sieve learns $s$-term DNF formulas under the uniform distribution in time polynomial in $n$, $s$ and $1/\varepsilon$, and Bshouty and Jackson adapted it to uniform quantum superpositions of labelled examples.
Problem. Is there a learner and a polynomial $p$ such that, for all $n, s \ge 1$, every $f \in \mathcal{D}_{n,s}$ and all $\varepsilon, \delta \in (0, 1/2)$, the learner runs in time at most $p(n, s, 1/\varepsilon, \log(1/\delta))$ and, with probability at least $1 - \delta$ over the examples and its own randomness, outputs $h$ with $$\Pr_{X}\bigl(h(X) \ne f(X)\bigr) \le \varepsilon,$$ where $X$ is a fresh uniform point of $\{0,1\}^n$?
Source: Valiant (1984), who posed the learning of DNF formulas in the PAC model; the uniform-distribution question from random examples alone is discussed by Yang, Blum and Carbonell (2013), §1.2. Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- ST — Statistics Theory
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, Boolean functions, DNF formulas, PAC learning
References
@article{valiant1984,
author = {Valiant, L. G.},
title = {A theory of the learnable},
journal = {Comm. ACM},
volume = {27},
number = {11},
year = {1984},
pages = {1134--1142},
doi = {10.1145/1968.1972},
}
@inproceedings{yang2013,
author = {Yang, Liu and Blum, Avrim and Carbonell, Jaime},
title = {Learnability of {DNF} with representation-specific queries},
booktitle = {Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (ITCS 2013)},
publisher = {ACM},
address = {New York},
year = {2013},
pages = {37--46},
doi = {10.1145/2422436.2422441},
}
@inproceedings{verbeurgt1990,
author = {Verbeurgt, Karsten},
title = {Learning {DNF} under the uniform distribution in quasi-polynomial time},
booktitle = {Proceedings of the Third Annual Workshop on Computational Learning Theory (COLT 1990)},
publisher = {Morgan Kaufmann},
year = {1990},
pages = {314--326},
doi = {10.1016/B978-1-55860-146-8.50027-8},
}
@article{jackson1997,
author = {Jackson, Jeffrey C.},
title = {An efficient membership-query algorithm for learning {DNF} with respect to the uniform distribution},
journal = {J. Comput. System Sci.},
volume = {55},
number = {3},
year = {1997},
pages = {414--440},
doi = {10.1006/jcss.1997.1533},
}
@article{bshouty1999,
author = {Bshouty, Nader H. and Jackson, Jeffrey C.},
title = {Learning {DNF} over the uniform distribution using a quantum example oracle},
journal = {SIAM J. Comput.},
volume = {28},
number = {3},
year = {1999},
pages = {1136--1153},
doi = {10.1137/S0097539795293123},
}
@misc{aim-classical-uniform-dnf-learning,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Polynomial-time DNF learning from uniform random examples}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/326-classical-uniform-dnf-learning.md},
note = {Entry 326 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00284, "Polynomial-time DNF learning from uniform random examples", clopen.solutions.