__
TR01-006 | 18th October 2000 00:00
__

#### On Learning Monotone DNF under Product Distributions

**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.