Learning Random Monotone DNF.
J. Jackson and H. Lee and R. Servedio and A. Wan.
Discrete Applied Mathematics, 159(5), 2011, pp. 259-271.
Preliminary version in 12th International Workshop on Randomness and Computation (RANDOM), 2008, pp. 483--497.


Abstract:

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.

pdf of conference version

pdf of journal version


Back to main papers page