{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T04:27:52Z","timestamp":1743827272837},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"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":["Quantum Inf Process"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s11128-021-03158-1","type":"journal-article","created":{"date-parts":[[2021,6,25]],"date-time":"2021-06-25T07:02:37Z","timestamp":1624604557000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Parity decision tree in classical\u2013quantum separations for certain classes of Boolean functions"],"prefix":"10.1007","volume":"20","author":[{"given":"Chandra Sekhar","family":"Mukherjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subhamoy","family":"Maitra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,25]]},"reference":[{"key":"3158_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Ambainis, A.: Forrelation: a problem that optimally sepa-rates quantum from classical computing. In: Proceedings of STOC\u20192015 (2015)","DOI":"10.1145\/2746539.2746547"},{"key":"3158_CR2","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Superlinear advantage for exact quantum algorithms. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing. ACM Press, New York, pp. 891\u2013900 (2013)","DOI":"10.1145\/2488608.2488721"},{"key":"3158_CR3","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Balodis, K., Belovs, A., Lee, T., Santha, M., Smotrovs, J.: Separations in query complexity based on pointer functions. J. ACM 64, 5, Article 32 (2017)","DOI":"10.1145\/3106234"},{"key":"3158_CR4","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Iraids, J., Nagaj, D.: Exact quantum query complexity of $${\\sf EXACT^n_{k,l}}$$. Theory and practice of computer science. SOFSEM 2017. LNCS, vol 10139, (2017)","DOI":"10.1007\/978-3-319-51963-0_19"},{"key":"3158_CR5","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum query complexity and semi-definite programming. In: Proceedings of 18th IEEE Annual Conference on Computational Complexity, pp. 179\u2013193 (2003)"},{"issue":"4","key":"3158_CR6","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. ACM 48(4), 778\u2013797 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"3158_CR7","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. Theoret. Comput. Sci. 288(1), 21\u201343 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"3158_CR8","doi-asserted-by":"crossref","unstructured":"Camion, P., Carlet, C., Charpin, P., Sendrier, N.: On correlation-immune functions. In Proceedings, LNCS Advances in Cryptology: Crypto 1991, Vol. 576, Springer, Berlin, pp. 86\u2013100 (1991)","DOI":"10.1007\/3-540-46766-1_6"},{"key":"3158_CR9","doi-asserted-by":"crossref","unstructured":"Chen, W., Li, L., Ye, Z.: Characterization of exact one-query quantum algorithms. Phys. Rev. A 101, 022325 (2020)","DOI":"10.1103\/PhysRevA.101.022325"},{"key":"3158_CR10","unstructured":"Dillon, J. F.: Elementary Hadamard Difference sets. Ph.D. Dissertation, University of Maryland (1974)"},{"issue":"2","key":"3158_CR11","doi-asserted-by":"publisher","first-page":"189","DOI":"10.3390\/e23020189","volume":"23","author":"G Xu","year":"2021","unstructured":"Xu, G., Qiu, D.: Partial Boolean functions with exact quantum query complexity one. Entropy 23(2), 189 (2021)","journal-title":"Entropy"},{"key":"3158_CR12","doi-asserted-by":"crossref","unstructured":"Goos, M., Pitassi, T., Watson, T.: Deterministic communication vs. partition number. In: Proceedings of FOCS\u20192015","DOI":"10.1109\/FOCS.2015.70"},{"key":"3158_CR13","unstructured":"Grant, M., Boyd, S.: CVH: Matlab software for disciplined convex programming, version 1.21. http:\/\/cvxr.com\/cvx, (2011)"},{"key":"3158_CR14","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1007\/s00453-013-9826-8","volume":"71","author":"A Montanaro","year":"2015","unstructured":"Montanaro, A., Jozsa, R., Mitchison, G.: On exact quantum query complexity. Algorithmica 71, 775\u2013796 (2015)","journal-title":"Algorithmica"},{"key":"3158_CR15","doi-asserted-by":"crossref","unstructured":"Raz, R.: Exponential separation of quantum and classical communication complexity. In: Proceedings of STOC\u20191999","DOI":"10.1145\/301250.301343"},{"key":"3158_CR16","doi-asserted-by":"crossref","unstructured":"Sarkar, P., Maitra, S.: Construction of nonlinear boolean functions with important cryptographic properties. Advances in Cryptology\u2013Eurocrypt 2000. LNCS, vol 1807, pp. 485\u2013506 (2000)","DOI":"10.1007\/3-540-45539-6_35"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03158-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03158-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03158-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,5]],"date-time":"2021-07-05T08:30:18Z","timestamp":1625473818000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03158-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6]]},"references-count":16,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["3158"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03158-1","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6]]},"assertion":[{"value":"20 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"218"}}