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 from random examples only. This is an exponential improvement over the best previous polynomial-time algorithms in this model, which could learn monotone $o(\log^2 n)$-term DNF. We also show that various classes of small constant-depth circuits which compute monotone functions are PAC learnable in polynomial time under the uniform distribution. All of our results extend to learning under any constant-bounded product distribution.
pdf of conference version
Postscript or pdf of journal version