{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:56:41Z","timestamp":1757620601671,"version":"3.44.0"},"publisher-location":"Singapore","reference-count":22,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819502141"},{"type":"electronic","value":"9789819502158"}],"license":[{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-0215-8_15","type":"book-chapter","created":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T16:25:07Z","timestamp":1753979107000},"page":"193-205","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Average-Case Deterministic Query Complexity of Boolean Functions with\u00a0Fixed Weight"],"prefix":"10.1007","author":[{"given":"Yuan","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haowei","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,1]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A., de Wolf, R.: Average-case quantum query complexity. J. Phys. Math. Gen. 34(35), 6741 (2001)","DOI":"10.1088\/0305-4470\/34\/35\/302"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21\u201343 (2002)","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Ben-David, S., Kothari, R.: Separations in query complexity using cheat sheets. In: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 863\u2013876 (2016)","DOI":"10.1145\/2897518.2897644"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Ben-David, S., Kothari, R., Rao, S., Tal, A.: \u201cDegree vs. approximate degree and quantum implications of Huang\u2019s sensitivity theorem\u201d. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1330\u20131342 (2021)","DOI":"10.1145\/3406325.3451047"},{"issue":"3","key":"15_CR5","doi-asserted-by":"publisher","first-page":"949","DOI":"10.4007\/annals.2019.190.3.6","volume":"190","author":"H Huang","year":"2019","unstructured":"Huang, H.: Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Ann. Math. 190(3), 949\u2013955 (2019)","journal-title":"Ann. Math."},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Rossman, B.: \u201cOn the constant-depth complexity of k-clique\u201d. In: Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 721\u2013730 (2008)","DOI":"10.1145\/1374376.1374480"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Rossman, B.: The monotone complexity of k-clique on random graphs. SIAM J. Comput. 43(1), 256\u2013279 (2014)","DOI":"10.1137\/110839059"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Probabilistic computations: toward a unified measure of complexity. In: 18th Annual Symposium on Foundations of Computer Science (sfcs 977), pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Saks, M., Schramm, O., Servedio, R.A.: Every decision tree has an influential variable. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905), pp. 31\u201339 (2005)","DOI":"10.1109\/SFCS.2005.34"},{"key":"15_CR10","unstructured":"Lee, H.K.: Decision trees and influence: an inductive proof of the OSSS inequality. Theor. Comput. 6(1), 81\u201384 (2010)"},{"key":"15_CR11","unstructured":"Jain, R., Zhang, S.: The influence lower bound via query elimination. In: arXiv preprint arXiv:1102.4699 (2011)"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Benjamini, I., Schramm, O., Wilson, D.B.: Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read. In: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. (2005)","DOI":"10.1145\/1060590.1060627"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Servedio, R.A.: Learning monotone decision trees in polynomial time. In: 21st Annual IEEE Conference on Computational Complexity (CCC\u201906), pp. 213\u2013225 (2006)","DOI":"10.1109\/CCC.2006.25"},{"issue":"5","key":"15_CR14","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1080\/00029890.2007.11920428","volume":"114","author":"Y Peres","year":"2007","unstructured":"Peres, Y., Schramm, O., Sheffield, S., Wilson, D.B.: Randomturn hex and other selection games. Am. Math. Mon. 114(5), 373\u2013387 (2007)","journal-title":"Am. Math. Mon."},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"729","DOI":"10.4310\/MRL.2001.v8.n6.a4","volume":"8","author":"S Smirnov","year":"2001","unstructured":"Smirnov, S., Werner, W.: Critical exponents for twodimensional percolation. Math. Res. Lett. 8, 729\u2013744 (2001)","journal-title":"Math. Res. Lett."},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/s00037-016-0139-6","volume":"25","author":"A Ambainis","year":"2016","unstructured":"Ambainis, A.: Quantum query complexity of almost all functions with fixed on-set size. Comput. Complex. 25, 723\u2013735 (2016)","journal-title":"Comput. Complex."},{"key":"15_CR17","unstructured":"H\u00e5stad, J.: Computational limitations for small depth circuits. PhD thesis. Massachusetts Institute of Technology (1986)"},{"key":"15_CR18","unstructured":"Rossman, B.: An entropy proof of the switching lemma and tight bounds on the decision-tree size of AC0. (2017). URL: https:\/\/users.cs.duke.edu\/~br148\/logsize.pdf"},{"key":"15_CR19","unstructured":"Rossman, B.: Criticality of regular formulas. In: 34th Computational Complexity Conference (CCC 2019). vol. 137, pp. 1:1\u20131:28 (2019)"},{"key":"15_CR20","unstructured":"Harsha, P., Molli, T., Shankar, A.: Criticality of AC0-Formulae. In: 38th Computational Complexity Conference (CCC 2023) Leibniz International Proceedings in Informatics (LIPIcs), vol. 264, pp. 19:1\u201319:24 (2023)"},{"key":"15_CR21","unstructured":"O\u2019Donnell, R.: Analysis of Boolean functions. Cambridge University Press (2014)"},{"issue":"5","key":"15_CR22","doi-asserted-by":"publisher","first-page":"1699","DOI":"10.1137\/120897432","volume":"43","author":"J H\u00e5stad","year":"2014","unstructured":"H\u00e5stad, J.: On the correlation of parity and small-depth circuits. SIAM J. Comput. 43(5), 1699\u20131708 (2014)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-0215-8_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T09:37:10Z","timestamp":1757324230000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-0215-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,1]]},"ISBN":["9789819502141","9789819502158"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-0215-8_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,8,1]]},"assertion":[{"value":"1 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/cocoon2025\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}