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. This is an exponential improvement over previous algorithms in this model, which could learn monotone $o(\log^2 n)$-term DNF, and is the first efficient algorithm for monotone $(\log n)^{\omega(1)}$-term ... more >>>

Producing a small DNF expression consistent with given data is a classical problem in computer science that occurs in a number of forms and has numerous applications. We consider two standard variants of this problem. The first one is two-level logic minimization or finding a minimal DNF formula consistent with ... more >>>