A. Klivans and R. Servedio.

Preliminary version in

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