On Learning Read-K-Satisfy-J DNF
Abstract
We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k•j=O(logn/loglogn). Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size > 2W(n). Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].
Cite
Text
Blum et al. "On Learning Read-K-Satisfy-J DNF." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181051Markdown
[Blum et al. "On Learning Read-K-Satisfy-J DNF." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/blum1994colt-learning/) doi:10.1145/180139.181051BibTeX
@inproceedings{blum1994colt-learning,
title = {{On Learning Read-K-Satisfy-J DNF}},
author = {Blum, Avrim and Khardon, Roni and Kushilevitz, Eyal and Pitt, Leonard and Roth, Dan},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1994},
pages = {110-117},
doi = {10.1145/180139.181051},
url = {https://mlanthology.org/colt/1994/blum1994colt-learning/}
}