Learning DNF in Time 2^{O(n^{1/3})}.
A. Klivans and R. Servedio.
Journal of Computer and System Sciences 68(2), 2004, pp. 303-318 (special issue for STOC 2001).
Preliminary version in 33rd Annual Symposium on Theory of Computing (STOC), 2001, pp. 258-265.
Best Student Paper award, STOC 2001.


Using techniques from learning theory, we show that any $s$-term DNF over $n$ variables can be computed by a polynomial threshold function of degree $O(n^{1/3} \log s)$. This upper bound matches, up to a logarithmic factor, the longstanding lower bound given by Minsky and Papert in their 1968 book {\em Perceptrons}. As a consequence of this upper bound we obtain the fastest known algorithm for learning polynomial size DNF, one of the central problems in computational learning theory.

pdf of conference version

Postscript or pdf of journal version

Back to main papers page