{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T16:31:32Z","timestamp":1754152292632,"version":"3.41.2"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T00:00:00Z","timestamp":1738800000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T00:00:00Z","timestamp":1738800000000},"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":["comput. complex."],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s00037-025-00263-w","type":"journal-article","created":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T02:31:22Z","timestamp":1738809082000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Fine-Grained Query Complexity of Symmetric Functions"],"prefix":"10.1007","volume":"34","author":[{"given":"Supartha","family":"Podder","sequence":"first","affiliation":[]},{"given":"Penghui","family":"Yao","sequence":"additional","affiliation":[]},{"given":"Zekun","family":"Ye","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,6]]},"reference":[{"key":"263_CR1","doi-asserted-by":"crossref","unstructured":"Scott Aaronson & Andris Ambainis (2014). The Need for Structure\nin Quantum Speedups. Theory of Computing 10, 133\u2013166.","DOI":"10.4086\/toc.2014.v010a006"},{"key":"263_CR2","doi-asserted-by":"crossref","unstructured":"Scott Aaronson & Andris Ambainis (2018). Forrelation: A problem\nthat optimally separates quantum from classical computing. SIAM\nJournal on Computing 47(3), 982\u20131038.","DOI":"10.1137\/15M1050902"},{"key":"263_CR3","unstructured":"Scott Aaronson & Shalev Ben-David (2016). Sculpting Quantum\nSpeedups. In Proceedings of the 31st Conference on Computational\nComplexity, volume 50, 26:1\u201326:28."},{"key":"263_CR4","doi-asserted-by":"crossref","unstructured":"Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas\nRao & Avishay Tal (2021). Degree vs. approximate degree and Quantum\nimplications of Huang\u2019s sensitivity theorem. In Proceedings of the\n53rd Annual ACM SIGACT Symposium on Theory of Computing, 1330\u2013\n1342. ACM.","DOI":"10.1145\/3406325.3451047"},{"key":"263_CR5","unstructured":"Scott Aaronson, Robin Kothari, William Kretschmer &\nJustin Thaler (2020). Quantum lower bounds for approximate counting\nvia Laurent polynomials. In Proceedings of the 35th Computational\nComplexity Conference, 7:1\u20137:47."},{"key":"263_CR6","doi-asserted-by":"crossref","unstructured":"Jos\u00e9 A. Adell & Pedro Jodr\u00e1 (2006). Exact Kolmogorov and\ntotal variation distances between some familiar discrete distributions.\nJournal of Inequalities and Applications 2006, 1\u20138.","DOI":"10.1155\/JIA\/2006\/64307"},{"key":"263_CR7","doi-asserted-by":"crossref","unstructured":"Andris Ambainis (2007). Quantum Walk Algorithm for Element Distinctness.\nSIAM Journal of Computing 37(1), 210\u2013239.","DOI":"10.1137\/S0097539705447311"},{"key":"263_CR8","doi-asserted-by":"crossref","unstructured":"Andris Ambainis & Janis Iraids (2016). Optimal One-shot Quantum\nAlgorithm for EQUALITY and AND. Baltic Journal of Modern\nComputing 4(4).","DOI":"10.22364\/bjmc.2016.4.4.09"},{"key":"263_CR9","doi-asserted-by":"crossref","unstructured":"Arturs Backurs & Mohammad Bavarian (2014). On the Sum of\nL1 Influences. In Proceedings of the IEEE 29th Conference on Computational\nComplexity, 132\u2013143.","DOI":"10.1109\/CCC.2014.21"},{"key":"263_CR10","doi-asserted-by":"crossref","unstructured":"Nikhil Bansal & Makrand Sinha (2021). k-Forrelation optimally\nseparates quantum and classical query complexity. In Proccedings of\nthe 53rd Annual ACM SIGACT Symposium on Theory of Computing,\n1303\u20131316.","DOI":"10.1145\/3406325.3451040"},{"key":"263_CR11","doi-asserted-by":"crossref","unstructured":"Robert Beals, Harry Buhrman, Richard Cleve, Michele\nMosca & Ronald de Wolf (2001). Quantum lower bounds by polynomials.\nJournal of the ACM 48(4), 778\u2013797.","DOI":"10.1145\/502090.502097"},{"key":"263_CR12","unstructured":"Shalev Ben-David (2016). The Structure of Promises in Quantum\nSpeedups. In Proceedings of the 11th Conference on the Theory of Quantum\nComputation, Communication and Cryptography, volume 61, 7:1\u2013\n7:14."},{"key":"263_CR13","unstructured":"Shalev Ben-David (2021). Lecture 6: The Polynomial Method.\nhttps:\/\/cs.uwaterloo.ca\/~s4bendav\/CS867QIC890\/CS867QIC890W21week4notes.pdf\n."},{"key":"263_CR14","doi-asserted-by":"crossref","unstructured":"Shalev Ben-David, Andrew M. Childs, Andr\u00e1s Gily\u00e9n,\nWilliam Kretschmer, Supartha Podder & Daochen Wang\n(2020). Symmetries, Graph Properties, and Quantum Speedups. In\nProceedings of the 61st IEEE Annual Symposium on Foundations of\nComputer Science, 649\u2013660.","DOI":"10.1109\/FOCS46700.2020.00066"},{"key":"263_CR15","doi-asserted-by":"crossref","unstructured":"Gilles Brassard, Peter H\u00f8yer, Michele Mosca & Alain Tapp\n(2002). Quantum amplitude amplification and estimation. Contemporary\nMathematics 305, 53\u201374.","DOI":"10.1090\/conm\/305\/05215"},{"key":"263_CR16","doi-asserted-by":"crossref","unstructured":"Gilles Brassard, Peter H\u00f8yer & Alain Tapp (1998). Quantum\nCryptanalysis of Hash and Claw-Free Functions. In LATIN 1998: Theoretical\nInformatics, Third Latin American Symposium, volume 1380,\n163\u2013169.","DOI":"10.1007\/BFb0054319"},{"key":"263_CR17","doi-asserted-by":"crossref","unstructured":"Sergey Bravyi, David Gosset, Robert K\u00f6nig & Marco\nTomamichel (2019). Quantum Advantage with Noisy Shallow Circuits\nin 3D. In Proccedings of the 60th IEEE Annual Symposium on\nFoundations of Computer Science, 995\u2013999.","DOI":"10.1109\/FOCS.2019.00064"},{"key":"263_CR18","unstructured":"Andr\u00e9 Chailloux (2019). A Note on the Quantum Query Complexity\nof Permutation Symmetric Functions. In Proceedings of the 10th\nInnovations in Theoretical Computer Science Conference, volume 124,\n19:1\u201319:7."},{"key":"263_CR19","doi-asserted-by":"crossref","unstructured":"Sitan Chen, Jordan Cotler, Hsin-Yuan Huang & Jerry Li\n(2021). Exponential Separations Between Learning With and Without\nQuantum Memory. In Proccedings of the 62nd IEEE Annual Symposium\non Foundations of Computer Science, 574\u2013585.","DOI":"10.1109\/FOCS52979.2021.00063"},{"key":"263_CR20","doi-asserted-by":"crossref","unstructured":"Byung-Soo Choi (2012). Optimality proofs of quantum weight decision\nalgorithms. Quantum Information Processing 11(1), 123\u2013136.","DOI":"10.1007\/s11128-011-0233-2"},{"key":"263_CR21","doi-asserted-by":"crossref","unstructured":"David Deutsch & Richard Jozsa (1992). Rapid solution of problems\nby quantum computation. Proceedings of the Royal Society of London.\nSeries A: Mathematical, Physical and Engineering Sciences 439(1907),\n553\u2013558.","DOI":"10.1098\/rspa.1992.0167"},{"key":"263_CR22","unstructured":"Bill Fefferman & Shelby Kimmel (2018). Quantum vs. Classical\nProofs and Subset Verification. In Proceedings of the 43rd International\nSymposium on Mathematical Foundations of Computer Science, volume\n117, 22:1\u201322:23."},{"key":"263_CR23","doi-asserted-by":"crossref","unstructured":"Yuval Filmus, Hamed Hatami, Nathan Keller & Noam Lifshitz\n(2016). On the Sum of L1 Influences of bounded functions. Israel\nJournal of Mathematics 214(1), 167\u2013192.","DOI":"10.1007\/s11856-016-1355-0"},{"key":"263_CR24","doi-asserted-by":"crossref","unstructured":"Justin Gilmer, Michael E. Saks & Srikanth Srinivasan (2013).\nComposition Limits and Separating Examples for Some Boolean Function\nComplexity Measures. In Proceedings of the 28th Conference on\nComputational Complexity, 185\u2013196. IEEE Computer Society.","DOI":"10.1109\/CCC.2013.27"},{"key":"263_CR25","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser & Michael Sipser (1986). Private coins versus\npublic coins in interactive proof systems. In Proceedings of the 18th\nannual ACM symposium on Theory of computing, 59\u201368.","DOI":"10.1145\/12130.12137"},{"key":"263_CR26","doi-asserted-by":"crossref","unstructured":"Daniel Grier & Luke Schaeffer (2020). Interactive shallow Clifford\ncircuits: quantum advantage against NC1 and beyond. In Proccedings\nof the 52nd Annual ACM SIGACT Symposium on Theory of\nComputing, 875\u2013888.","DOI":"10.1145\/3357713.3384332"},{"key":"263_CR27","doi-asserted-by":"crossref","unstructured":"L. K. Grover (1996). A fast quantum mechanical algorithm for\ndatabase search. In Proceedings of the 28th IEEE Annual Symposium\non Theory of Computing, 212\u2013219.","DOI":"10.1145\/237814.237866"},{"key":"263_CR28","doi-asserted-by":"crossref","unstructured":"Buhrman Harry & Ronald de Wolf (2002). Complexity measures\nand decision tree complexity: a survey. Theoretical Computer Science\n288(1), 21\u201343.","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"263_CR29","doi-asserted-by":"crossref","unstructured":"Xiaoyu He, Xiaoming Sun, Guang Yang & Pei Yuan (2023). Exact\nquantum query complexity of weight decision problems. Science\nChina Information Sciences 66, 129 503. Also see arXiv:1801.05717.","DOI":"10.1007\/s11432-021-3468-x"},{"key":"263_CR30","doi-asserted-by":"crossref","unstructured":"Susan Holmes (2004). Stein\u2019s method for birth and death chains. IMS\nLecture Notes-Monograph Series 46, 45\u201367.","DOI":"10.1214\/lnms\/1196283799"},{"key":"263_CR31","doi-asserted-by":"crossref","unstructured":"Kazuo Iwama, Harumichi Nishimura, Rudy Raymond & Shigeru\nYamashita (2007a). Unbounded-Error Classical and Quantum Communication\nComplexity. In Proceedings of the 18th International Symposium\non Algorithms and Computation, ISAAC 2007, volume 4835,\n100\u2013111.","DOI":"10.1007\/978-3-540-77120-3_11"},{"key":"263_CR32","doi-asserted-by":"crossref","unstructured":"Kazuo Iwama, Harumichi Nishimura, Rudy Raymond & Shigeru\nYamashita (2007b). Unbounded-Error One-Way Classical and Quantum\nCommunication Complexity. In Proceedings of the 34th International\nColloquium on Automata, Languages and Programming, ICALP\n2007, volume 4596, 110\u2013121.","DOI":"10.1007\/978-3-540-73420-8_12"},{"key":"263_CR33","unstructured":"Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss &\nAmir Yehudayoff (2021). Tight bounds on the Fourier growth of\nbounded functions on the hypercube. arXiv preprint arXiv:2107.06309."},{"key":"263_CR34","doi-asserted-by":"crossref","unstructured":"John Kallaugher (2021). A Quantum Advantage for a Natural\nStreaming Problem. In Proccedings of the 62nd IEEE Annual Symposium\non Foundations of Computer Science, 897\u2013908.","DOI":"10.1109\/FOCS52979.2021.00091"},{"key":"263_CR35","unstructured":"Pascal Koiran, Vincent Nesme & Natacha Portier (2006). On\nthe Probabilistic Query Complexity of Transitively Symmetric Problems.\nhttps:\/\/hal.science\/hal-00120934v2\/document\n."},{"key":"263_CR36","unstructured":"Jasper Lee (2020). Lecture 11: Distinguishing (Discrete) Distributions.\nhttps:\/\/cs.brown.edu\/courses\/csci1951-w\/lec\/lec201120notes.pdf\n."},{"key":"263_CR37","doi-asserted-by":"crossref","unstructured":"Vladimir I. Levenshtein (1995). Krawtchouk polynomials and universal\nbounds for codes and designs in Hamming spaces. IEEE Transactions\non Information Theory 41(5), 1303\u20131321.","DOI":"10.1109\/18.412678"},{"key":"263_CR38","unstructured":"Shachar Lovett & Jiapeng Zhang (2023). Fractional Certificates\nfor Bounded Functions. In Proceedings of the 14th Innovations in Theoretical\nComputer Science Conference, volume 251, 84:1\u201384:13."},{"key":"263_CR39","unstructured":"Florence Jessie MacWilliams & Neil James Alexander\nSloane (1977). The theory of error-correcting codes, volume 16. Elsevier."},{"key":"263_CR40","doi-asserted-by":"crossref","unstructured":"John C. Mason & David C. Handscomb (2002). Chebyshev polynomials.\nCRC Press.","DOI":"10.1201\/9781420036114"},{"key":"263_CR41","unstructured":"Rajat Mittal, Sanjay S. Nair & Sunayana Patro (2021). Lower\nbounds on quantum query complexity for symmetric functions. arXiv\npreprint arXiv:2110.12616."},{"key":"263_CR42","doi-asserted-by":"crossref","unstructured":"Ashley Montanaro, Richard Jozsa & Graeme Mitchison\n(2015). On Exact Quantum Query Complexity. Algorithmica 71(4),\n775\u2013796.","DOI":"10.1007\/s00453-013-9826-8"},{"key":"263_CR43","doi-asserted-by":"crossref","unstructured":"Ashley Montanaro, Harumichi Nishimura & Rudy Raymond\n(2008). Unbounded-Error Quantum Query Complexity. In Proceedings\nof the 19th International Symposium on Algorithms and Computation,\nISAAC 2008, volume 5369, 919\u2013930.","DOI":"10.1007\/978-3-540-92182-0_80"},{"key":"263_CR44","unstructured":"Ryan O\u2019Donnell (2015). Lecture 17: Discriminating Two\nQuantum States. https:\/\/www.cs.cmu.edu\/~odonnell\/quantum15\/lecture17.pdf\n."},{"key":"263_CR45","doi-asserted-by":"crossref","unstructured":"Ramamohan Paturi (1992). On the Degree of Polynomials that Approximate\nSymmetric Boolean Functions (Preliminary Version). In Proceedings\nof the 24th Annual ACM Symposium on Theory of Computing,\n468\u2013474. ACM.","DOI":"10.1145\/129712.129758"},{"key":"263_CR46","unstructured":"Daowen Qiu & Shenggen Zheng (2016). Characterizations of symmetrically\npartial Boolean functions with exact quantum query complexity.\narXiv preprint arXiv:1603.06505."},{"key":"263_CR47","doi-asserted-by":"crossref","unstructured":"Daowen Qiu & Shenggen Zheng (2018). Generalized Deutsch\u2013Jozsa\nproblem and the optimal quantum algorithm. Physical Review A 97(6),\n062 331.","DOI":"10.1103\/PhysRevA.97.062331"},{"key":"#cr-split#-263_CR48.1","doi-asserted-by":"crossref","unstructured":"Daowen Qiu & Shenggen Zheng (2020). Revisiting Deutsch-Jozsa","DOI":"10.1016\/j.ic.2020.104605"},{"key":"#cr-split#-263_CR48.2","unstructured":"algorithm. Information and Computation 2020(275), 104 605."},{"key":"263_CR49","doi-asserted-by":"crossref","unstructured":"Alexander A. Sherstov (2009). Approximate Inclusion-Exclusion\nfor Arbitrary Symmetric Functions. Computational Complexity 18(2),\n219\u2013247.","DOI":"10.1007\/s00037-009-0274-4"},{"key":"263_CR50","doi-asserted-by":"crossref","unstructured":"Alexander A. Sherstov, Andrey A. Storozhenko & Pei Wu\n(2021). An optimal separation of randomized and quantum query complexity.\nIn Proccedings of the 53rd Annual ACM SIGACT Symposium\non Theory of Computing, 1289\u20131302.","DOI":"10.1145\/3406325.3451019"},{"key":"263_CR51","doi-asserted-by":"crossref","unstructured":"Peter W. Shor (1994). Algorithms for quantum computation: Discrete\nlogarithms and factoring. In Proceedings of the 35th Annual Symposium\non Foundations of Computer Science, 124\u2013134.","DOI":"10.1109\/SFCS.1994.365700"},{"key":"263_CR52","doi-asserted-by":"crossref","unstructured":"Daniel R. Simon (1994). On the power of quantum computation. In\nProceedings of the 35th Annual Symposium on Foundations of Computer\nScience, 116\u2013123.","DOI":"10.1109\/SFCS.1994.365701"},{"key":"263_CR53","doi-asserted-by":"crossref","unstructured":"Avishay Tal (2013). Properties and applications of Boolean function\ncomposition. In Proceedings of the 4th conference on Innovations in\nTheoretical Computer Science, 441\u2013454. ACM.","DOI":"10.1145\/2422436.2422485"},{"key":"263_CR54","doi-asserted-by":"crossref","unstructured":"Avishay Tal (2020). Towards optimal separations between quantum\nand randomized query complexities. In Proccedings of the 61st Annual\nSymposium on Foundations of Computer Science, 228\u2013239.","DOI":"10.1109\/FOCS46700.2020.00030"},{"key":"263_CR55","doi-asserted-by":"crossref","unstructured":"Ronald de Wolf (2008). A note on quantum algorithms and the minimal\ndegree of \u025b-error polynomials for symmetric functions. Quantum\nInformation and Computation 8(10), 943\u2013950.","DOI":"10.26421\/QIC8.10-4"},{"key":"263_CR56","doi-asserted-by":"crossref","unstructured":"Takashi Yamakawa & Mark Zhandry (2022). Verifiable Quantum\nAdvantage without Structure. In Proceedings of the 63rd IEEE Annual\nSymposium on Foundations of Computer Science, 69\u201374.","DOI":"10.1109\/FOCS54457.2022.00014"},{"key":"263_CR57","doi-asserted-by":"crossref","unstructured":"Christof Zalka (2000). Grover\u2019s quantum searching algorithm is\noptimal. Physical Review A 60(4), 2746.","DOI":"10.1103\/PhysRevA.60.2746"},{"key":"263_CR58","doi-asserted-by":"crossref","unstructured":"Mark Zhandry (2015). A note on the quantum collision and set\nequality problems. Quantum Information and Computation 15(7&8),\n557\u2013567.","DOI":"10.26421\/QIC15.7-8-2"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00263-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00263-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00263-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T23:10:54Z","timestamp":1753139454000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00263-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,6]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["263"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00263-w","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,2,6]]},"assertion":[{"value":"7 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"3"}}