{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T02:46:30Z","timestamp":1773542790054,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,5,1]],"date-time":"2010-05-01T00:00:00Z","timestamp":1272672000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2010,5]]},"DOI":"10.1007\/s00493-010-2173-3","type":"journal-article","created":{"date-parts":[[2010,9,22]],"date-time":"2010-09-22T04:37:36Z","timestamp":1285130256000},"page":"327-358","source":"Crossref","is-referenced-by-count":28,"title":["New degree bounds for polynomial threshold functions"],"prefix":"10.1007","volume":"30","author":[{"given":"Ryan","family":"O\u2019Donnell","sequence":"first","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,9,23]]},"reference":[{"key":"2173_CR1","doi-asserted-by":"crossref","unstructured":"A. Ambainis, A. Childs, B. Reichardt, R. Spalek and S. Zhang: Any ANDOR formula of size n can be evaluated in time n 1\/2+o(1) on a quantum computer, in: Proc. 48th IEEE Symposium on Foundations of Computer Science (FOCS), pages 363\u2013372, 2007.","DOI":"10.1109\/FOCS.2007.4389507"},{"key":"2173_CR2","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"D. Angluin: Queries and concept learning, Machine Learning 2 (1988), 319\u2013342.","journal-title":"Machine Learning"},{"issue":"2","key":"2173_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01215346","volume":"14","author":"J. Aspnes","year":"1994","unstructured":"J. Aspnes, R. Beigel, M. Furst and S. Rudich: The expressive power of voting polynomials, Combinatorica 14(2) (1994), 1\u201314.","journal-title":"Combinatorica"},{"key":"2173_CR4","doi-asserted-by":"crossref","unstructured":"R. Beigel: The polynomial method in circuit complexity, in: Proceedings of the Eigth Conference on Structure in Complexity Theory, pages 82\u201395, 1993.","DOI":"10.1109\/SCT.1993.336538"},{"key":"2173_CR5","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF01263422","volume":"4","author":"R. Beigel","year":"1994","unstructured":"R. Beigel: Perceptrons, PP, and the Polynomial Hierarchy, Computational Complexity 4 (1994), 339\u2013349.","journal-title":"Computational Complexity"},{"issue":"2","key":"2173_CR6","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1006\/jcss.1995.1017","volume":"50","author":"R. Beigel","year":"1995","unstructured":"R. Beigel, N. Reingold and D. Spielman: PP is closed under intersection, Journal of Computer & System Sciences 50(2) (1995), 191\u2013202.","journal-title":"Journal of Computer & System Sciences"},{"issue":"2","key":"2173_CR7","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1137\/0403015","volume":"3","author":"J. Bruck","year":"1990","unstructured":"J. Bruck: Harmonic analysis of polynomial threshold functions, SIAM Journal on Discrete Mathematics 3(2) (1990), 168\u2013177.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2173_CR8","doi-asserted-by":"crossref","unstructured":"H. Buhrman, R. Cleve and A. Wigderson: Quantum vs. classical communication and computation, in: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pages 63\u201368. ACM Press, 1998.","DOI":"10.1145\/276698.276713"},{"issue":"1","key":"2173_CR9","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H. Buhrman","year":"2002","unstructured":"H. Buhrman and R. de Wolf: Complexity measures and decision tree complexity: a survey; Theoretical Computer Science 288(1) (2002), 21\u201343.","journal-title":"Theoretical Computer Science"},{"key":"2173_CR10","volume-title":"Introduction to approximation theory","author":"E. Cheney","year":"1966","unstructured":"E. Cheney: Introduction to approximation theory, McGraw-Hill, New York, New York, 1966."},{"key":"2173_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-010-2196-8","volume-title":"Advanced Combinatorics: The Art of Finite and Infinite Expansions","author":"L. Comtet","year":"1974","unstructured":"L. Comtet: Advanced Combinatorics: The Art of Finite and Infinite Expansions; Reidel, Dordrecht, Netherlands, 1974."},{"issue":"2","key":"2173_CR12","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1006\/inco.1995.1136","volume":"121","author":"Y. Freund","year":"1995","unstructured":"Y. Freund: Boosting a weak learning algorithm by majority, Information and Computation 121(2) (1995), 256\u2013285.","journal-title":"Information and Computation"},{"issue":"6","key":"2173_CR13","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0020-0190(97)00141-5","volume":"63","author":"M. Goldmann","year":"1997","unstructured":"M. Goldmann: On the power of a threshold gate at the top, Information Processing Letters 63(6) (1997), 287\u2013293.","journal-title":"Information Processing Letters"},{"key":"2173_CR14","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0022-0000(93)90001-D","volume":"46","author":"A. Hajnal","year":"1993","unstructured":"A. Hajnal, W. Maass, P. Pudl\u00e1k, M. Szegedy and Gy. Tur\u00e1n: Threshold circuits of bounded depth, Journal of Computer and System Sciences 46 (1993), 129\u2013154.","journal-title":"Journal of Computer and System Sciences"},{"key":"2173_CR15","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An introduction to computational learning theory","author":"M. Kearns","year":"1994","unstructured":"M. Kearns and U. Vazirani: An introduction to computational learning theory. MIT Press, Cambridge, MA, 1994."},{"key":"2173_CR16","doi-asserted-by":"crossref","unstructured":"A. Klivans, R. O\u2019Donnell and R. Servedio: Learning intersections and thresholds of halfspaces, in: Proceedings of the 43rd Annual Symposium on Foundations of Computer Science, pages 177\u2013186, 2002.","DOI":"10.1109\/SFCS.2002.1181894"},{"key":"2173_CR17","doi-asserted-by":"crossref","unstructured":"A. Klivans and R. Servedio: Learning DNF in time 2\u00d5(n1\/3), in: Proceedings of the Thirty-Third Annual Symposium on Theory of Computing, pages 258\u2013265, 2001.","DOI":"10.1145\/380752.380809"},{"issue":"4","key":"2173_CR18","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1007\/s000370050015","volume":"7","author":"M. Krause","year":"1998","unstructured":"M. Krause and P. Pudl\u00e1k: Computing boolean functions by polynomials and threshold circuits, Computational Complexity 7(4) (1998), 346\u2013370.","journal-title":"Computational Complexity"},{"issue":"3","key":"2173_CR19","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"N. Linial, Y. Mansour and N. Nisan: Constant depth circuits, Fourier transform and learnability; Journal of the ACM 40(3) (1993), 607\u2013620.","journal-title":"Journal of the ACM"},{"key":"2173_CR20","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"N. Littlestone: Learning quickly when irrelevant attributes abound: a new linearthreshold algorithm; Machine Learning 2 (1988), 285\u2013318.","journal-title":"Machine Learning"},{"key":"2173_CR21","volume-title":"Perceptrons: an introduction to computational geometry (expanded edition)","author":"M. Minsky","year":"1988","unstructured":"M. Minsky and S. Papert: Perceptrons: an introduction to computational geometry (expanded edition); MIT Press, Cambridge, MA, 1988."},{"key":"2173_CR22","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1307\/mmj\/1028999029","volume":"11","author":"D. J. Newman","year":"1964","unstructured":"D. J. Newman: Rational approximation to |x|, Michigan Mathematical Journal 11 (1964), 11\u201314.","journal-title":"Michigan Mathematical Journal"},{"key":"2173_CR23","doi-asserted-by":"crossref","unstructured":"N. Nisan and M. Szegedy: On the degree of Boolean functions as real polynomials, in: Proceedings of the Twenty-Fourth Annual Symposium on Theory of Computing, pages 462\u2013467, 1992.","DOI":"10.1145\/129712.129757"},{"key":"2173_CR24","doi-asserted-by":"crossref","unstructured":"R. O\u2019Donnell and R. Servedio: New degree bounds for polynomial threshold functions, in: Proceedings of the 35th ACM Symposium on Theory of Computing, pages 325\u2013334, 2003.","DOI":"10.1145\/780542.780592"},{"issue":"2","key":"2173_CR25","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1006\/inco.1994.1059","volume":"112","author":"R. Paturi","year":"1994","unstructured":"R. Paturi and M. Saks: Approximating threshold circuits by rational functions, Information and Computation 112(2) (1994), 257\u2013272.","journal-title":"Information and Computation"},{"key":"2173_CR26","doi-asserted-by":"crossref","unstructured":"M. Saks: Slicing the hypercube, in: Surveys in Combinatorics 1993 (Keith Walker, ed.), London Mathematical Society Lecture Note Series 187, pages 211\u2013257, 1993.","DOI":"10.1017\/CBO9780511662089.009"},{"issue":"3","key":"2173_CR27","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1016\/j.jcss.2007.06.014","volume":"74","author":"D. Sieling","year":"2008","unstructured":"D. Sieling: Minimization of decision trees is hard to approximate, Journal of Computer and System Sciences 74(3) (2008), 394\u2013403.","journal-title":"Journal of Computer and System Sciences"},{"issue":"11","key":"2173_CR28","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"L. Valiant: A theory of the learnable, Communications of the ACM 27(11) (1984), 1134\u20131142.","journal-title":"Communications of the ACM"},{"key":"2173_CR29","doi-asserted-by":"crossref","unstructured":"N. Vereshchagin: Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP, in: Proceedings of the Third Annual Israel Symposium on Theory of Computing and Systems, pages 46\u201351, 1995.","DOI":"10.1109\/ISTCS.1995.377047"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2173-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-010-2173-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2173-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T23:53:52Z","timestamp":1740527632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-010-2173-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["2173"],"URL":"https:\/\/doi.org\/10.1007\/s00493-010-2173-3","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5]]}}}