ECCC-Report TR01-006https://eccc.weizmann.ac.il/report/2001/006Comments and Revisions published for TR01-006en-usTue, 09 Jan 2001 19:55:23 +0200
Paper TR01-006
| On Learning Monotone DNF under Product Distributions |
Rocco Servedio
https://eccc.weizmann.ac.il/report/2001/006We 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.
Tue, 09 Jan 2001 19:55:23 +0200https://eccc.weizmann.ac.il/report/2001/006