Theory of Computing
-------------------
Title     : On Learning Random DNF Formulas Under the Uniform Distribution
Authors   : Jeffrey C. Jackson and Rocco A. Servedio
Volume    : 2
Number    : 8
Pages     : 147-172
URL       : http://www.theoryofcomputing.org/articles/v002a008

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 non-monotone 
  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 learn a broad class of 
  polynomial-size DNF in a reasonable average-case model of learning 
  from random examples.