On Learning Random DNF Formulas under the Uniform Distribution.
J. Jackson and R. Servedio.
Theory of Computing 2, 2006, pp. 147--172.
Preliminary version in 9th International Workshop on Randomness and Computation (RANDOM), 2005, pp. 342--353.

Abstract:

We study the average-case learnability of DNF formulas in the model of learning from uniformly distributed random examples. We define a natural model of random monotone DNF formulas and give an efficient algorithm which with high probability can learn, for any fixed constant $\gamma>0$, a random $t$-term monotone DNF for any $t = O(n^{2-\gamma}).$ We also define a model of random nonmonotone DNF and give an efficient algorithm which with high probability can learn a random $t$-term DNF for any $t=O(n^{3/2 - \gamma}).$ These are the first known algorithms that can successfully learn a broad class of polynomial-size DNF in a reasonable average-case model of learning from random examples.