{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T09:53:52Z","timestamp":1772272432254,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,12,22]],"date-time":"2016-12-22T00:00:00Z","timestamp":1482364800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s00493-015-2987-0","type":"journal-article","created":{"date-parts":[[2016,12,22]],"date-time":"2016-12-22T01:20:59Z","timestamp":1482369659000},"page":"419-464","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the degree of univariate polynomials over the integers"],"prefix":"10.1007","volume":"37","author":[{"given":"Gil","family":"Cohen","sequence":"first","affiliation":[]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[]},{"given":"Avishay","family":"Tal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,12,22]]},"reference":[{"key":"2987_CR1","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1112\/plms\/83.3.532","volume":"83","author":"R. C. Baker","year":"2001","unstructured":"R. C. Baker, G. Harman and J. Pintz: The difference between consecutive primes, II, Proceedings of the London Mathematical Society 83 (2001), 532\u2013562.","journal-title":"Proceedings of the London Mathematical Society"},{"key":"2987_CR2","first-page":"82","volume-title":"Structure in Complexity Theory Conference","author":"R. Beigel","year":"1993","unstructured":"R. Beigel: The polynomial method in circuit complexity, in: Structure in Complexity Theory Conference, 82\u201395, 1993."},{"key":"2987_CR3","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, Theor. Comput. Sci. 288 (2002), 21\u201343.","journal-title":"Theor. Comput. Sci."},{"key":"2987_CR4","doi-asserted-by":"crossref","first-page":"23","DOI":"10.4064\/aa-2-1-23-46","volume":"2","author":"H. Cram\u00e9r","year":"1936","unstructured":"H. Cram\u00e9r: On the order of magnitude of the difference between consecutive prime numbers, Acta Arithmetica 2 (1936), 23\u201346.","journal-title":"Acta Arithmetica"},{"key":"2987_CR5","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W. Feller","year":"1968","unstructured":"W. Feller: An Introduction to Probability Theory and Its Applications, volume 1, Wiley, New York, 3rd edition, 1968.","edition":"3"},{"key":"2987_CR6","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF01215917","volume":"17","author":"J. Gathen von zur","year":"1997","unstructured":"J. von zur Gathen and J. R. Roche: Polynomials with two values, Combinatorica 17 (1997), 345\u2013362.","journal-title":"Combinatorica"},{"key":"2987_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804106","volume-title":"Computational Complexity: A Conceptual Perspective","author":"O. Goldreich","year":"2008","unstructured":"O. Goldreich: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008."},{"key":"2987_CR8","volume-title":"Computing with Polynomials over Composites","author":"P. Gopalan","year":"2006","unstructured":"P. Gopalan: Computing with Polynomials over Composites, PhD thesis, Georgia Institute of Technology, August 2006."},{"key":"2987_CR9","volume-title":"Geometry of Numbers","author":"P. M. Gruber","year":"1987","unstructured":"P. M. Gruber and C. G. Lekkerkerker: Geometry of Numbers, North-Holland, 1987."},{"key":"2987_CR10","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching, Addison-Wesley, 1973."},{"key":"2987_CR11","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s00493-009-2310-z","volume":"29","author":"M. N. Kolountzakis","year":"2009","unstructured":"M. N. Kolountzakis, R. J. Lipton, E. Markakis, A. Mehta and N. K. Vishnoi: On the Fourier spectrum of symmetric Boolean functions, Combinatorica 29 (2009), 363\u2013387.","journal-title":"Combinatorica"},{"key":"2987_CR12","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, J. ACM 40 (1993), 607\u2013620.","journal-title":"J. ACM"},{"key":"2987_CR13","doi-asserted-by":"crossref","first-page":"184","DOI":"10.2307\/2369308","volume":"1","author":"E. Lucas","year":"1878","unstructured":"E. Lucas: Th\u00e9orie des fonctions num\u00e9riques simplement p\u00e9riodiques, American Journal of Mathematics 1 (1878), 184\u2013196.","journal-title":"American Journal of Mathematics"},{"key":"2987_CR14","volume-title":"Chebyshev Polynomials","author":"J. C. Mason","year":"2003","unstructured":"J. C. Mason and D. C. Handscomb: Chebyshev Polynomials, Chapman & Hall\/CRC, Boca Raton, FL, 2003."},{"key":"2987_CR15","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1016\/j.jcss.2004.04.002","volume":"69","author":"E. Mossel","year":"2004","unstructured":"E. Mossel, R. O\u2019Donnell and R. A. Servedio: Learning functions of k relevant variables, J. Comput. Syst. Sci. 69 (2004), 421\u2013434.","journal-title":"J. Comput. Syst. Sci."},{"key":"2987_CR16","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 on the size of bounded depth circuits over a complete basis with logical addition, Math. Notes 41 (1987), 333\u2013338.","journal-title":"Math. Notes"},{"key":"2987_CR17","doi-asserted-by":"crossref","first-page":"26","DOI":"10.2307\/2308012","volume":"62","author":"H. Robbins","year":"1955","unstructured":"H. Robbins: A Remark of Stirling\u2019s Formula, American Mathematical Monthly 62 (1955), 26\u201329.","journal-title":"American Mathematical Monthly"},{"key":"2987_CR18","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/s00493-014-2875-z","volume":"34","author":"A. Shpilka","year":"2014","unstructured":"A. Shpilka and A. Tal: On the minimal Fourier degree of symmetric Boolean functions, Combinatorica 34 (2014), 359\u2013377.","journal-title":"Combinatorica"},{"key":"2987_CR19","first-page":"77","volume-title":"Proceedings of the 19th Annual STOC","author":"R. Smolensky","year":"1987","unstructured":"R. Smolensky: Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in: Proceedings of the 19th Annual STOC, pages 77\u201382, 1987."},{"key":"2987_CR20","volume-title":"Determinants and Their Applications in Mathematical Physics","author":"R. Vein","year":"1999","unstructured":"R. Vein and P. Dale: Determinants and Their Applications in Mathematical Physics, Springer, 1999."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-015-2987-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-2987-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-2987-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,16]],"date-time":"2019-09-16T16:51:33Z","timestamp":1568652693000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-015-2987-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,22]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["2987"],"URL":"https:\/\/doi.org\/10.1007\/s00493-015-2987-0","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,22]]}}}