{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T06:06:07Z","timestamp":1743055567323,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030794156"},{"type":"electronic","value":"9783030794163"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79416-3_25","type":"book-chapter","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T18:03:46Z","timestamp":1623866626000},"page":"406-421","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Separation Between the Degree of\u00a0a\u00a0Boolean Function and the Block Sensitivity"],"prefix":"10.1007","author":[{"given":"Nikolay V.","family":"Proskurin","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"25_CR1","doi-asserted-by":"publisher","unstructured":"Beigel, R.: Perceptrons, pp, and the polynomial hierarchy. Comput. Complex. 4, 339\u2013349 (1994). https:\/\/doi.org\/10.1007\/BF01263422","DOI":"10.1007\/BF01263422"},{"key":"25_CR2","doi-asserted-by":"publisher","unstructured":"Bogdanov, A., Mande, N.S., Thaler, J., Williamson, C.: Approximate degree, secret sharing, and concentration phenomena. In: Achlioptas, D., V\u00e9gh, L.A. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2019, September 20\u201322, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA. LIPIcs, vol. 145, pp. 71:1\u201371:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2019.71,https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2019.71","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2019.71,"},{"key":"25_CR3","doi-asserted-by":"publisher","unstructured":"Borwein, P., Erdelyi, T.: Polynomials and Polynomial Inequalities. Graduate Texts in Mathematics, Springer, New York (1995). https:\/\/doi.org\/10.1007\/978-1-4612-0793-1. https:\/\/books.google.ru\/books?id=386CC7JnuuwC","DOI":"10.1007\/978-1-4612-0793-1"},{"key":"25_CR4","doi-asserted-by":"publisher","unstructured":"Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21\u201343 (2002). https:\/\/doi.org\/10.1016\/S0304-3975(01)00144-X","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"25_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-642-39206-1_26","volume-title":"Automata, Languages, and Programming","author":"M Bun","year":"2013","unstructured":"Bun, M., Thaler, J.: Dual lower bounds for approximate degree and Markov-Bernstein inequalities. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 303\u2013314. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39206-1_26"},{"key":"25_CR6","unstructured":"Cohen, G., Shpilka, A.: On the degree of symmetric functions on the boolean cube. Electron. Colloquium Comput. Complex. 17, 39 (2010). http:\/\/eccc.hpi-web.de\/report\/2010\/039"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Ehlich, H., Zeller, K.: Schwankung von polynomen zwischen gitterpunkten. Mathematische Zeitschrift, pp. 41\u201344 (1964)","DOI":"10.1007\/BF01111276"},{"key":"25_CR8","doi-asserted-by":"publisher","unstructured":"von zur Gathen, J., Roche, J.R.: Polynomials with two values. Comb. 17(3), 345\u2013362 (1997). https:\/\/doi.org\/10.1007\/BF01215917","DOI":"10.1007\/BF01215917"},{"key":"25_CR9","doi-asserted-by":"publisher","unstructured":"Hatami, P., Kulkarni, R., Pankratov, D.: Variations on the sensitivity conjecture. Theory Comput. 4, 1\u201327 (2011). https:\/\/doi.org\/10.4086\/toc.gs.2011.004","DOI":"10.4086\/toc.gs.2011.004"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Huang, H.: Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Ann. Math. 190(3), 949\u2013955 (2019). https:\/\/www.jstor.org\/stable\/10.4007\/annals.2019.190.3.6","DOI":"10.4007\/annals.2019.190.3.6"},{"key":"25_CR11","doi-asserted-by":"publisher","unstructured":"Jukna, S.: Boolean Function Complexity - Advances and Frontiers, Algorithms and Combinatorics, vol. 27. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-24508-4","DOI":"10.1007\/978-3-642-24508-4"},{"key":"25_CR12","unstructured":"Midrijanis, G.: Exact quantum query complexity for total Boolean functions. arXiv preprint quant-ph\/0403168 (2004)"},{"key":"25_CR13","unstructured":"Minsky, M., Papert, S.: Perceptrons - An Introduction to Computational Geometry. MIT Press (1987)"},{"key":"25_CR14","doi-asserted-by":"publisher","unstructured":"Nisan, N., Szegedy, M.: On the degree of Boolean functions as real polynomials. Comput. Complex. 4, 301\u2013313 (1994). https:\/\/doi.org\/10.1007\/BF01263419","DOI":"10.1007\/BF01263419"},{"key":"25_CR15","unstructured":"Proskurin, N.: Symmetrization linprog (2020). https:\/\/colab.research.google.com\/drive\/1XKJSYLElVxGgZuwHaFy4BdoTN4JIgKXJ?usp=sharing"},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"Rivlin, T.J., Cheney, E.W.: A comparison of uniform approximations on an interval and a finite subset thereof. SIAM J. Numer. Anal. 3(2), 311\u2013320 (1966). http:\/\/www.jstor.org\/stable\/2949624","DOI":"10.1137\/0703024"},{"key":"25_CR17","unstructured":"Shadrin, A.: Twelve proofs of the Markov inequality. Approximation theory: a volume dedicated to Borislav Bojanov, pp. 233\u2013298 (2004)"},{"key":"25_CR18","unstructured":"Spalek, R.: A dual polynomial for OR. CoRR abs\/0803.4516 (2008). http:\/\/arxiv.org\/abs\/0803.4516"},{"key":"25_CR19","doi-asserted-by":"publisher","unstructured":"Tal, A.: Properties and applications of Boolean function composition. In: Kleinberg, R.D. (ed.) Innovations in Theoretical Computer Science, ITCS 20113, Berkeley, CA, USA, January 9\u201312, 2013, pp. 441\u2013454. ACM (2013). https:\/\/doi.org\/10.1145\/2422436.2422485","DOI":"10.1145\/2422436.2422485"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79416-3_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T23:24:40Z","timestamp":1623972280000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79416-3_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030794156","9783030794163"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79416-3_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"17 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sochi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"68","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}