Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR01-006 | 18th October 2000 00:00

#### On Learning Monotone DNF under Product Distributions

TR01-006
Authors: Rocco Servedio
Publication: 9th January 2001 19:55
Keywords:

Abstract:

We show that the class of monotone $2^{O(\sqrt{\log n})}$-term DNF
formulae can be PAC learned in polynomial time under the uniform
distribution. This is an exponential improvement over previous
algorithms in this model, which could learn monotone
$o(\log^2 n)$-term DNF, and is the first efficient algorithm
for monotone $(\log n)^{\omega(1)}$-term DNF in any nontrivial
model of learning from random examples. Our result extends to any
constant-bounded product distribution.

ISSN 1433-8092 | Imprint