{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:05:20Z","timestamp":1764781520644,"version":"3.46.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,11,8]],"date-time":"2025-11-08T00:00:00Z","timestamp":1762560000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2025,11,8]],"date-time":"2025-11-08T00:00:00Z","timestamp":1762560000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00037-025-00266-7","type":"journal-article","created":{"date-parts":[[2025,11,8]],"date-time":"2025-11-08T17:37:30Z","timestamp":1762623450000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Pseudo-Deterministic Query Complexity of Search Problems"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-3110-3584","authenticated-orcid":false,"given":"Arkadev","family":"Chattopadhyay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7338-1762","authenticated-orcid":false,"given":"Yogesh","family":"Dahiya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9116-4398","authenticated-orcid":false,"given":"Meena","family":"Mahajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,11,8]]},"reference":[{"key":"266_CR1","doi-asserted-by":"crossref","unstructured":"Michael Alekhnovich & Alexander A. Razborov (2001). Lower Bounds for Polynomial Calculus: Non-Binomial Case. In 42nd Annual Symposium on Foundations of Computer Science FOCS, 190-199. IEEE Computer Society.","DOI":"10.1109\/SFCS.2001.959893"},{"key":"266_CR2","doi-asserted-by":"crossref","unstructured":"Paul Beame, Richard Karp, Toniann Pitassi & Michael Saks (2002). The efficiency of resolution and Davis-Putnam procedures. SIAM Journal on Computing 31(4), 1048-1075.","DOI":"10.1137\/S0097539700369156"},{"key":"266_CR3","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson & Nicola Galesi (2003). Space complexity of random formulae in resolution. Random Structures & Algorithms 23(1), 92-109.","DOI":"10.1002\/rsa.10089"},{"key":"266_CR4","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Russell Impagliazzo & Avi Wigderson (2004). Near optimal separation of tree-like and general resolution. Combinatorica 24(4), 585-603.","DOI":"10.1007\/s00493-004-0036-5"},{"key":"266_CR5","doi-asserted-by":"publisher","unstructured":"Eli Ben-Sasson & Avi Wigderson (2001). Short proofs are narrow-resolution made simple. J. ACM 48(2), 149-169. URL https:\/\/doi.org\/10.1145\/375827.375835.","DOI":"10.1145\/375827.375835"},{"key":"266_CR6","doi-asserted-by":"crossref","unstructured":"Olaf Beyersdorff, Nicola Galesi & Massimo Lauria (2013). A characterization of tree-like resolution size. Information Processing Letters 113(18), 666-671.","DOI":"10.1016\/j.ipl.2013.06.002"},{"key":"266_CR7","doi-asserted-by":"crossref","unstructured":"Harry Buhrman & Ronald De Wolf (2002). Complexity measures and decision tree complexity: a survey. Theoretical Computer Science 288(1), 21-43.","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"266_CR8","doi-asserted-by":"crossref","unstructured":"Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo & Toniann Pitassi (2001). Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes. J. Comput. Syst. Sci. 62(2), 267-289.","DOI":"10.1006\/jcss.2000.1726"},{"key":"266_CR9","doi-asserted-by":"crossref","unstructured":"Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S Mande, Jaikumar Radhakrishnan & Swagato Sanyal (2023). Randomized versus Deterministic Decision Tree Size. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 867-880.","DOI":"10.1145\/3564246.3585199"},{"key":"266_CR10","doi-asserted-by":"publisher","unstructured":"Vasek Chv\u00e1tal & Endre Szemer\u00e9di (1988). Many Hard Examples for Resolution. J. ACM 35(4), 759-768. URL https:\/\/doi.org\/10.1145\/48014.48016.","DOI":"10.1145\/48014.48016"},{"key":"266_CR11","unstructured":"Daniel Dadush & Samarth Tiwari (2020). On the Complexity of Branching Proofs. In 35th Computational Complexity Conference (CCC 2020), Shubhangi Saraf, editor, volume 169 of Leibniz International Proceedings in Informatics (LIPIcs), 34:1-34:35. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. ISBN 978-3-95977-156-6. ISSN 1868-8969. URL https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2020\/12586."},{"key":"266_CR12","doi-asserted-by":"crossref","unstructured":"Uriel Feige, David Peleg, Prabhakar Raghavan & Eli Upfal (1990). Computing with unreliable information. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, 128-137.","DOI":"10.1145\/100216.100230"},{"key":"266_CR13","doi-asserted-by":"crossref","unstructured":"Ankit Garg, Mika G\u00f6\u00f6s, Pritish Kamath & Dmitry Sokolov (2018). Monotone circuit lower bounds from resolution. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 902-911.","DOI":"10.1145\/3188745.3188838"},{"key":"266_CR14","unstructured":"Eran Gat & Shafi Goldwasser (2011). Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications. Electron. Colloquium Comput. Complex. 136."},{"key":"266_CR15","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Shafi Goldwasser & Dana Ron (2013). On the possibilities and limitations of pseudodeterministic algorithms. In Innovations in Theoretical Computer Science ITCS, Robert D. Kleinberg, editor, 127-138. ACM. See also ECCC Vol. 19, T.R. 12-101, 2012.","DOI":"10.1145\/2422436.2422453"},{"key":"266_CR16","unstructured":"Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi & Rahul Santhanam (2021). On the Pseudo-Deterministic Query Complexity of NP Search Problems. In 36th Computational Complexity Conference CCC, Valentine Kabanets, editor, volume 200 of LIPIcs, 36:1-36:22. Schloss Dagstuhl - Leibniz-Zentrum f\"ur Informatik."},{"key":"266_CR17","doi-asserted-by":"crossref","unstructured":"Dima Grigoriev (1998). Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. In 39th Annual Symposium on Foundations of Computer Science FOCS, 648-652. IEEE Computer Society.","DOI":"10.1109\/SFCS.1998.743515"},{"key":"266_CR18","unstructured":"Hao Huang (2019). Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. CoRR abs\/1907.00847. URL https:\/\/arxiv.org\/abs\/1907.00847."},{"key":"266_CR19","doi-asserted-by":"publisher","unstructured":"Stasys Jukna (2012). Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer. ISBN 978-3-642-24507-7. URL https:\/\/doi.org\/10.1007\/978-3-642-24508-4.","DOI":"10.1007\/978-3-642-24508-4"},{"key":"266_CR20","doi-asserted-by":"crossref","unstructured":"Alexander Knop, Shachar Lovett, Sam McGuire & Weiqiang Yuan (2021a). Guest Column: Models of computation between decision trees and communication. ACM SIGACT News 52(2), 46-70.","DOI":"10.1145\/3471469.3471479"},{"key":"266_CR21","doi-asserted-by":"crossref","unstructured":"Alexander Knop, Shachar Lovett, Sam McGuire & Weiqiang Yuan (2021b). Log-rank and lifting for AND-functions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 197-208.","DOI":"10.1145\/3406325.3450999"},{"key":"266_CR22","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz, Moni Naor, Ilan Newman & Avi Wigderson (1995). Search problems in the decision tree model. SIAM Journal on Discrete Mathematics 8(1), 119-132.","DOI":"10.1137\/S0895480192233867"},{"key":"266_CR23","doi-asserted-by":"crossref","unstructured":"Ilan Newman (1991). Private vs. common random bits in communication complexity. Information processing letters 39(2), 67-71.","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"266_CR24","doi-asserted-by":"crossref","unstructured":"Noam Nisan (1989). CREW PRAMs and decision trees. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, 327-335.","DOI":"10.1145\/73007.73038"},{"key":"266_CR25","unstructured":"Noam Nisan (1993). The communication complexity of threshold gates. Combinatorics, Paul Erdos is Eighty 1(301-315), 6."},{"key":"266_CR26","unstructured":"Rahul Santhanam (April 2023). Personal communication."},{"key":"266_CR27","doi-asserted-by":"crossref","unstructured":"Andrew Chi-Chih Yao (1983). Lower Bounds by Probabilistic Arguments (Extended Abstract). In 24th Annual Symposium on Foundations of Computer Science FOCS, 420-428. IEEE Computer Society.","DOI":"10.1109\/SFCS.1983.30"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00266-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00266-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00266-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:00:16Z","timestamp":1764781216000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00266-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,8]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["266"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00266-7","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,11,8]]},"assertion":[{"value":"16 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"20"}}