{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T18:43:43Z","timestamp":1763664223310},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T00:00:00Z","timestamp":1583280000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T00:00:00Z","timestamp":1583280000000},"content-version":"vor","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":[[2020,4]]},"DOI":"10.1007\/s00493-019-4136-7","type":"journal-article","created":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T05:50:56Z","timestamp":1583301056000},"page":"237-244","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function"],"prefix":"10.1007","volume":"40","author":[{"given":"John","family":"Chiarelli","sequence":"first","affiliation":[]},{"given":"Pooya","family":"Hatami","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Saks","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,4]]},"reference":[{"key":"4136_CR1","doi-asserted-by":"publisher","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 (2002), no. 1, 21\u201343.","journal-title":"Theoretical Computer Science"},{"key":"4136_CR2","volume-title":"Boolean constant degree functions on the slice are juntas","author":"Y Filmus","year":"2018","unstructured":"Y. Filmus and F. Ihringer: Boolean constant degree functions on the slice are juntas, arXiv:1801.06338 (2018)."},{"key":"4136_CR3","first-page":"1","volume":"4","author":"P Hatami","year":"2011","unstructured":"P. Hatami, R. Kulkarni and D. Pankratov: Variations on the sensitivity conjecture, Theory of Computing Library, Graduate Surveys 4 (2011), 1\u201327.","journal-title":"Theory of Computing Library, Graduate Surveys"},{"key":"4136_CR4","volume-title":"MIT press","author":"M L Minsky","year":"1988","unstructured":"M. L. Minsky and S. A. Papert: Perceptrons, MIT press (1988)."},{"key":"4136_CR5","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N Nisan","year":"1994","unstructured":"N. Nisan and M. Szegedy: On the degree of Boolean functions as real polynomials, Computational complexity 4 (1994), 301\u2013313.","journal-title":"Computational complexity"},{"key":"4136_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean functions","author":"R O\u2019Donnell","year":"2014","unstructured":"R. O\u2019DONNELL: Analysis of Boolean functions, Cambridge University Press, 2014."},{"key":"4136_CR7","volume-title":"Private communication","author":"I Shinkar","year":"2017","unstructured":"I. Shinkar and A. Tal: Private communication (2017)."},{"key":"4136_CR8","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1145\/2422436.2422485","volume-title":"Proceedings of the 4th conference on Innovations in Theoretical Computer Science, ACM","author":"A Tal","year":"2013","unstructured":"A. Tal: Properties and applications of Boolean function composition, Proceedings of the 4th conference on Innovations in Theoretical Computer Science, ACM, 2013, 441\u2013454."},{"key":"4136_CR9","volume-title":"Private Communication","author":"J Wellens","year":"2019","unstructured":"J. Wellens: Private Communication (2019)."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-4136-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-019-4136-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-4136-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T00:50:34Z","timestamp":1614819034000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-019-4136-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,4]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["4136"],"URL":"https:\/\/doi.org\/10.1007\/s00493-019-4136-7","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,4]]},"assertion":[{"value":"15 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}