Learning DNF in time 2 Õ(n 1/3 )

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.

Authors

• Adam R. Klivans
• Rocco A. Servedio

Keywords

No keywords are indexed for this paper.