{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T12:05:53Z","timestamp":1768305953833,"version":"3.49.0"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031522123","type":"print"},{"value":"9783031522130","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-52213-0_5","type":"book-chapter","created":{"date-parts":[[2024,1,13]],"date-time":"2024-01-13T10:02:29Z","timestamp":1705140149000},"page":"59-73","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Query Complexity Measures and\u00a0Their Relations for\u00a0Symmetric Functions"],"prefix":"10.1007","author":[{"given":"Rajat","family":"Mittal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-4187-9935","authenticated-orcid":false,"given":"Sanjay S.","family":"Nair","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sunayana","family":"Patro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,14]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","unstructured":"Aaronson, S.: Quantum certificate complexity. In: 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), Aarhus, Denmark, 7\u201310 July 2003, pp. 171\u2013178 (2003). https:\/\/doi.org\/10.1109\/CCC.2003.1214418","DOI":"10.1109\/CCC.2003.1214418"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"133","DOI":"10.4086\/toc.2014.v010a006","volume":"10","author":"S Aaronson","year":"2014","unstructured":"Aaronson, S., Ambainis, A.: The need for structure in quantum speedups. Theory Comput. 10, 133\u2013166 (2014). https:\/\/doi.org\/10.4086\/toc.2014.v010a006","journal-title":"Theory Comput."},{"key":"5_CR3","doi-asserted-by":"publisher","unstructured":"Aaronson, S., Ben-David, S., Kothari, R., Rao, S., Tal, A.: Degree vs. approximate degree and quantum implications of Huang\u2019s sensitivity theorem. In: STOC 2021: 53rd Symposium on Theory of Computing, Italy, 21\u201325 June 2021, pp. 1330\u20131342 (2021). https:\/\/doi.org\/10.1145\/3406325.3451047","DOI":"10.1145\/3406325.3451047"},{"key":"5_CR4","doi-asserted-by":"publisher","unstructured":"Aaronson, S., Rall, P.: Quantum approximate counting, simplified. In: 3rd Symposium on Simplicity in Algorithms, SOSA 2020, Salt Lake City, UT, USA, 6\u20137 January 2020, pp. 24\u201332 (2020). https:\/\/doi.org\/10.1137\/1.9781611976014.5","DOI":"10.1137\/1.9781611976014.5"},{"key":"5_CR5","doi-asserted-by":"publisher","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. In: Proceedings of the 32nd Symposium on Theory of Computing, Portland, OR, USA, 21\u201323 May 2000, pp. 636\u2013643 (2000). https:\/\/doi.org\/10.1145\/335305.335394","DOI":"10.1145\/335305.335394"},{"key":"5_CR6","doi-asserted-by":"publisher","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), pp. 230\u2013239 (2003). https:\/\/doi.org\/10.1109\/SFCS.2003.1238197","DOI":"10.1109\/SFCS.2003.1238197"},{"key":"5_CR7","doi-asserted-by":"publisher","unstructured":"Barnum, H., Saks, M.E., Szegedy, M.: Quantum query complexity and semi-definite programming. In: 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), Aarhus, Denmark, 7\u201310 July 2003, pp. 179\u2013193 (2003). https:\/\/doi.org\/10.1109\/CCC.2003.1214419","DOI":"10.1109\/CCC.2003.1214419"},{"key":"5_CR8","doi-asserted-by":"publisher","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. In: 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, Palo Alto, California, USA, 8\u201311 November 1998, pp. 352\u2013361 (1998). https:\/\/doi.org\/10.1109\/SFCS.1998.743485","DOI":"10.1109\/SFCS.1998.743485"},{"key":"5_CR9","doi-asserted-by":"publisher","unstructured":"Ben-David, S., Blais, E.: A tight composition theorem for the randomized query complexity of partial functions: extended abstract. In: 61st Symposium on Foundations of Computer Science, 2020, pp. 240\u2013246 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00031","DOI":"10.1109\/FOCS46700.2020.00031"},{"key":"5_CR10","doi-asserted-by":"publisher","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Quantum Computation and Information, pp. 53\u201374 (2002). https:\/\/doi.org\/10.1090\/conm\/305\/05215","DOI":"10.1090\/conm\/305\/05215"},{"issue":"1","key":"5_CR11","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H Buhrman","year":"2002","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","journal-title":"Theor. Comput. Sci."},{"key":"5_CR12","doi-asserted-by":"publisher","unstructured":"Chakraborty, S., G\u00e1l, A., Laplante, S., Mittal, R., Sunny, A.: Certificate games. In: Tauman Kalai, Y. (ed.) 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), vol. 251, pp. 32:1\u201332:24. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2023.32","DOI":"10.4230\/LIPIcs.ITCS.2023.32"},{"key":"5_CR13","doi-asserted-by":"publisher","unstructured":"Chakraborty, S., Kayal, C., Paraashar, M.: Separations between combinatorial measures for transitive functions. In: Boja\u0144czyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), vol. 229, pp. 36:1\u201336:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2022.36","DOI":"10.4230\/LIPIcs.ICALP.2022.36"},{"key":"5_CR14","unstructured":"Gavinsky, D., et al.: Quadratically tight relations for randomized query complexity. CoRR abs\/1708.00822 (2017). http:\/\/arxiv.org\/abs\/1708.00822"},{"key":"5_CR15","doi-asserted-by":"publisher","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Symposium on the Theory of Computing, 22\u201324 May 1996, pp. 212\u2013219 (1996). https:\/\/doi.org\/10.1145\/237814.237866","DOI":"10.1145\/237814.237866"},{"key":"5_CR16","doi-asserted-by":"publisher","unstructured":"Hoyer, P., Lee, T., Spalek, R.: Negative weights make adversaries stronger. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing - STOC 2007, p. 526 (2007). https:\/\/doi.org\/10.1145\/1250790.1250867","DOI":"10.1145\/1250790.1250867"},{"key":"5_CR17","first-page":"78","volume":"87","author":"P H\u00f8yer","year":"2005","unstructured":"H\u00f8yer, P., Spalek, R.: Lower bounds on quantum query complexity. Bull. EATCS 87, 78\u2013103 (2005)","journal-title":"Bull. EATCS"},{"key":"5_CR18","unstructured":"Huang, H.: Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. CoRR abs\/1907.00847 (2019). http:\/\/arxiv.org\/abs\/1907.00847"},{"key":"5_CR19","unstructured":"Kulkarni, R., Tal, A.: On fractional block sensitivity. Chic. J. Theor. Comput. Sci. 2016, 1\u201316 (2016). http:\/\/cjtcs.cs.uchicago.edu\/articles\/2016\/8\/contents.html"},{"key":"5_CR20","doi-asserted-by":"publisher","unstructured":"Laplante, S., Magniez, F.: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In: 19th Conference on Computational Complexity (CCC 2004), pp. 294\u2013304 (2004). https:\/\/doi.org\/10.1109\/CCC.2004.1313852","DOI":"10.1109\/CCC.2004.1313852"},{"key":"5_CR21","doi-asserted-by":"publisher","unstructured":"Lee, T., Mittal, R., Reichardt, B.W., Spalek, R., Szegedy, M.: Quantum query complexity of state conversion. In: 2011 Symposium on Foundations of Computer Science, pp. 344\u2013353 (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.75","DOI":"10.1109\/FOCS.2011.75"},{"key":"5_CR22","unstructured":"Mittal, R., Nair, S.S., Patro, S.: Lower bounds on quantum query complexity for symmetric functions (2021). https:\/\/arxiv.org\/abs\/2110.12616"},{"key":"5_CR23","doi-asserted-by":"publisher","unstructured":"Nayak, A., Wu, F.: The quantum query complexity of approximating the median and related statistics. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC 1999, pp. 384\u2013393. Association for Computing Machinery, New York (1999). https:\/\/doi.org\/10.1145\/301250.301349","DOI":"10.1145\/301250.301349"},{"issue":"4","key":"5_CR24","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N Nisan","year":"1994","unstructured":"Nisan, N., Szegedy, M.: On the degree of Boolean functions as real polynomials. Comput. Complex. 4(4), 301\u2013313 (1994). https:\/\/doi.org\/10.1007\/BF01263419","journal-title":"Comput. Complex."},{"key":"5_CR25","doi-asserted-by":"publisher","unstructured":"Paturi, R.: On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In: Proceedings of the Symposium on Theory of Computing, pp. 468\u2013474 (1992). https:\/\/doi.org\/10.1145\/129712.129758","DOI":"10.1145\/129712.129758"},{"key":"5_CR26","doi-asserted-by":"publisher","unstructured":"Simon, D.R.: On the power of quantum computation. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20\u201322 November 1994, pp. 116\u2013123 (1994). https:\/\/doi.org\/10.1109\/SFCS.1994.365701","DOI":"10.1109\/SFCS.1994.365701"},{"issue":"1","key":"5_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2006.v002a001","volume":"2","author":"R Spalek","year":"2006","unstructured":"Spalek, R., Szegedy, M.: All quantum adversary methods are equivalent. Theory Comput. 2(1), 1\u201318 (2006). https:\/\/doi.org\/10.4086\/toc.2006.v002a001","journal-title":"Theory Comput."},{"key":"5_CR28","doi-asserted-by":"publisher","unstructured":"Tal, A.: Properties and applications of Boolean function composition. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science - ITCS 2013, p. 441. ACM Press (2013). https:\/\/doi.org\/10.1145\/2422436.2422485","DOI":"10.1145\/2422436.2422485"},{"issue":"10","key":"5_CR29","doi-asserted-by":"publisher","first-page":"943","DOI":"10.26421\/QIC8.10-4","volume":"8","author":"R de Wolf","year":"2008","unstructured":"de Wolf, R.: A note on quantum algorithms and the minimal degree of $$\\epsilon $$-error polynomials for symmetric functions. Quantum Inf. Comput. 8(10), 943\u2013950 (2008). https:\/\/doi.org\/10.26421\/QIC8.10-4","journal-title":"Quantum Inf. Comput."},{"issue":"2\u20133","key":"5_CR30","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.tcs.2005.01.019","volume":"339","author":"S Zhang","year":"2005","unstructured":"Zhang, S.: On the power of Ambainis lower bounds. Theor. Comput. Sci. 339(2\u20133), 241\u2013256 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.01.019","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-52213-0_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T05:22:28Z","timestamp":1768281748000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-52213-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031522123","9783031522130"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-52213-0_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"14 January 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bhilai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 February 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 February 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.iitbhilai.ac.in\/caldam2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}