J. Jackson and H. Lee and R. Servedio and A. Wan.

Preliminary version in

We give an algorithm that with high probability properly learns random monotone $t(n)$-term DNF under the uniform distribution on the Boolean cube $\{0,1\}^n.$ For any polynomially bounded function $t(n) \leq$ poly$(n)$ the algorithm runs in time poly$(n,1/\eps)$ and with high probability outputs an $\eps$-accurate monotone DNF hypothesis.