Learning monotone log-term DNF formulas under the uniform distribution

Y. Sakai, A. Maruoka

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)


Based on the uniform distribution PAC learning model, the learnability for the class of monotone disjunctive normal form formulas with at most O (log n) terms, denoted O (log n)-term MDNF, is investigated. Using the technique of restriction, an algorithm that learns O (log n)-term MDNF by examples in polynomial time is given.

Original languageEnglish
Pages (from-to)17-33
Number of pages17
JournalTheory of Computing Systems
Issue number1
Publication statusPublished - 2000


Dive into the research topics of 'Learning monotone log-term DNF formulas under the uniform distribution'. Together they form a unique fingerprint.

Cite this