摘要: 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 logarithmic factor, the longstanding lower given Minsky and Papert in their 1968 book {\em Perceptrons}. As consequence this obtain fastest known algorithm for size DNF, one central problems computational theory.
core.ac.uk
acm.org
columbia.edu 
sci-hub.se 参考文章(36)
Tom Bylander, Worst-case analysis of the perceptron and exponentiated update algorithms Artificial Intelligence. ,vol. 106, pp. 335- 352 ,(1998) , 10.1016/S0004-3702(98)00098-8
R. Beigel, N. Reingold, D. Spielman, The perceptron strikes back structure in complexity theory annual conference. pp. 286- 291 ,(1991) , 10.1109/SCT.1991.160270
Karsten A. Verbeurgt, Learning Sub-classes of Monotone DNF on the Uniform Distribution algorithmic learning theory. pp. 385- 399 ,(1998) , 10.1007/3-540-49730-7_27
J. Tarui, T. Tsukiji, Learning DNF by approximating inclusion-exclusion formulae conference on computational complexity. pp. 215- 220 ,(1999) , 10.1109/CCC.1999.766279
Yoav Freund, Robert E. Schapire, Large margin classification using the perceptron algorithm conference on learning theory. ,vol. 37, pp. 209- 217 ,(1998) , 10.1145/279943.279985
James Aspnes, Richard Beigel, Merrick Furst, Steven Rudich, The expressive power of voting polynomials symposium on the theory of computing. pp. 402- 409 ,(1991) , 10.1145/103418.103461
Rocco A. Servedio, On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm Proceedings of the twelfth annual conference on Computational learning theory - COLT '99. pp. 296- 307 ,(1999) , 10.1145/307400.307474
L. G. Valiant, A theory of the learnable symposium on the theory of computing. ,vol. 27, pp. 1134- 1142 ,(1984) , 10.1145/800057.808710
Nader H. Bshouty, A subexponential exact learning algorithm for DNF using equivalence queries Information Processing Letters. ,vol. 59, pp. 37- 39 ,(1996) , 10.1016/0020-0190(96)00077-4
Avrim Blum, Rank- r decision trees are a subclass of r -decision lists Information Processing Letters. ,vol. 42, pp. 183- 185 ,(1992) , 10.1016/0020-0190(92)90237-P