Learning Random Monotone DNF Under the Uniform Distribution
Abstract
We show that randomly generated monotone c log(n)-DNF formula can be learned exactly in probabilistic polynomial time. Our notion of randomly generated is with respect to a uniform distribution. To prove this we identify the class of well behaved monotone c log(n)-DNF formulae, and show that almost every monotone DNF formula is well-behaved, and that there exists a probabilistic Turing machine that exactly learns all well behaved monotone c log(n)-DNF formula.
Cite
Text
Sellie. "Learning Random Monotone DNF Under the Uniform Distribution." Annual Conference on Computational Learning Theory, 2008.Markdown
[Sellie. "Learning Random Monotone DNF Under the Uniform Distribution." Annual Conference on Computational Learning Theory, 2008.](https://mlanthology.org/colt/2008/sellie2008colt-learning/)BibTeX
@inproceedings{sellie2008colt-learning,
title = {{Learning Random Monotone DNF Under the Uniform Distribution}},
author = {Sellie, Linda},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2008},
pages = {181-192},
url = {https://mlanthology.org/colt/2008/sellie2008colt-learning/}
}