Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-006 | 18th October 2000 00:00

On Learning Monotone DNF under Product Distributions

RSS-Feed




TR01-006
Authors: Rocco Servedio
Publication: 9th January 2001 19:55
Downloads: 3445
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