{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:28Z","timestamp":1781077648100,"version":"3.54.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1994,12,1]],"date-time":"1994-12-01T00:00:00Z","timestamp":786240000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1994,12]]},"DOI":"10.1007\/bf01263419","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T02:52:34Z","timestamp":1111632754000},"page":"301-313","source":"Crossref","is-referenced-by-count":210,"title":["On the degree of boolean functions as real polynomials"],"prefix":"10.1007","volume":"4","author":[{"given":"Noam","family":"Nisan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"J. Aspens, R. Beigel, M. Furst, and S. Rudich, On the expressive power of voting polynomials.Proc. Twenty-third Ann. ACM Symp. Theor. Comput., 1991, 402?409.","DOI":"10.1145\/103418.103461"},{"key":"CR2","unstructured":"R. Beigel, N. Reingold, and D. Spielman,The perceptron striles back. Technical report YALEU\/DCS\/TR-813, Yale University, 1990."},{"key":"CR3","unstructured":"J. Brook and R. Smolenski, Polynomial threshold functions,AC\u00b0 functions and spectral norms.Proc. 31st Ann. IEEE Symp. Found. Comput. Sci., 1990, 632?642."},{"key":"CR4","unstructured":"E. W. Cheney,Introduction to approximation theory. McGraw-Hill Book Co., 1966."},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, M. Kutylowski, R. Reischuk, Exact Time Bounds for Computing Boolean Functions on PRAMs Without Simultaneous Writes.Symp. Parallel Algorithms and Architecture, 1990, 125?137.","DOI":"10.1145\/97444.97678"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF01111276","volume":"86","author":"H. Ehlich","year":"1964","unstructured":"H. Ehlich andK. Zeller, Schwankung von Polynomen zwischen Gitterpunkten.Mathematische Zeitschrift 86 (1964), 41?44.","journal-title":"Mathematische Zeitschrift"},{"key":"CR7","unstructured":"J. von zur Gathen and J. Roche, Polynomials with two values.Preprint (1993)."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"J. Kahn, G. Kalai, and N. Linial, The influence of variables on Boolean functions.Proc. 29th Ann. IEEE Symp. Found. Comput. Sci., 1988, 68?80.","DOI":"10.1109\/SFCS.1988.21923"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"N. Linial, Y. Mansour, N. Nisan, Constant depth circuits, Fourier transform and Learnability.Proc. 30th Ann. IEEE Symp. Found. Comput. Sci., 1989, 574?579.","DOI":"10.1109\/SFCS.1989.63537"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and Y. Mansour, Learning decision trees using the Fourier transform.Proc. Twenty-third Ann. ACM Symp. Theor. Comput., 1991, 455?464.","DOI":"10.1145\/103418.103466"},{"key":"CR11","volume-title":"Perceptrons","author":"M. Minsky","year":"1988","unstructured":"M. Minsky andS. Papert,Perceptrons. MIT press, Cambridge, 1988 (Expanded edition). First edition appeared in 1968.","edition":"Expanded editio"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"N. Nisan, CREW PRAM's and decision trees.Proc. Twenty-first Ann. ACM Symp. Theor. Comput., 1989, 327?335.","DOI":"10.1145\/73007.73038"},{"issue":"4","key":"CR13","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A.A. Razborov","year":"1987","unstructured":"A.A. Razborov, Lower bounds for the size of circuits of bounded depth with basis (and,xor).Math. Notes of the Academy of Sciences of the USSR 41(4) (1987), 333?338.","journal-title":"Math. Notes of the Academy of Sciences of the USSR"},{"issue":"2","key":"CR14","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1137\/0703024","volume":"3","author":"T. J. Rivlin","year":"1966","unstructured":"T. J. Rivlin andE. W. Cheney, A comparison of Uniform Approximations on an interval and a finite subset thereof.SIAM J. Numer. Anal. 3(2) (1966), 311?320.","journal-title":"SIAM J. Numer. Anal."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"R. Smolenski, Algebraic methods in the theory of lower bounds for Boolean circuit complexity.Proc. Nineteenth Ann. ACM Symp. Theor. Comput., 1987, 77?82.","DOI":"10.1145\/28395.28404"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. T. Schwartz","year":"1980","unstructured":"J. T. Schwartz, Fast probabilistic Algorithms for verification of Polynomial identities.J. Assoc. Comput. Mach. 27 (1980), 701?717.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"I. Wegener,The complexity of Boolean functions. Wiley-Teubner Series in Comput. Sci., New York-Stuttgart, 1987.","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01263419.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01263419\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01263419","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T12:52:07Z","timestamp":1586177527000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01263419"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["BF01263419"],"URL":"https:\/\/doi.org\/10.1007\/bf01263419","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}