{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:05:08Z","timestamp":1764781508462,"version":"3.46.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T00:00:00Z","timestamp":1761177600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T00:00:00Z","timestamp":1761177600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive proofs asks whether Arthur-Merlin protocols can be simulated nondeterministically with a small overhead in time (the AM vs. NP problem). Both questions are intricately tied to lower bounds. Prominently, in both settings\n                    <jats:italic>blackbox<\/jats:italic>\n                    derandomization, i.e., derandomization through pseudorandom generators, has been shown equivalent to lower bounds for decision problems against circuits.\nRecently, Chen and Tell (FOCS'21) established nearequivalences in the BPP setting between\n                    <jats:italic>whitebox<\/jats:italic>\n                    derandomization and lower bounds for multi-bit functions against algorithms on almost-all inputs. The key ingredient is a technique to translate hardness into targeted hitting sets in an instance-wise fashion based on a layered arithmetization of the evaluation of a uniform circuit computing the hard function\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$f$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>f<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    on the given instance. Follow-up works managed to obtain full equivalences in the BPP setting by exploiting a\n                    <jats:italic>compression<\/jats:italic>\n                    property of classical pseudorandom generator constructions. In particular, Chen, Tell, and Williams (FOCS'23) showed that derandomization of BPP is equivalent to\n                    <jats:italic>constructive<\/jats:italic>\n                    lower bounds against algorithms that go through a compression phase.\nIn this paper, we develop a corresponding technique for Arthur-Merlin protocols and establish similar near-equivalences in the AM setting. As an example of our results in the hardness-to-derandomization direction, consider a length-preserving function\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$f$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>f<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    computable by a nondeterministic algorithm that runs in time\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n^a$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mi>a<\/mml:mi>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . We show that if every Arthur-Merlin protocol that runs in time\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n^c$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mi>c<\/mml:mi>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    for\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$c=O(\\log^2 a)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>c<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mo>log<\/mml:mo>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mi>a<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    can only compute\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$f$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>f<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    correctly on finitely many inputs, then AM is in NP. We also obtain equivalences between constructive lower bounds against Arthur-Merlin protocols that go through a compression phase and derandomization of AM via\n                    <jats:italic>targeted<\/jats:italic>\n                    generators. Our main technical contribution is the construction of suitable targeted hitting-set generators based on probabilistically checkable proofs of proximity for nondeterministic computations. \nAs a by-product of our constructions, we obtain the first result indicating that whitebox derandomization of AM may be equivalent to the existence of targeted hitting-set generators for AM, an issue raised by Goldreich (LNCS, 2011). By-products in the average-case setting include the first uniform hardness vs. randomness trade-offs for AM, as well as an unconditional mild derandomization result for AM.\n                  <\/jats:p>","DOI":"10.1007\/s00037-025-00279-2","type":"journal-article","created":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T13:23:29Z","timestamp":1761225809000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Instance-Wise Hardness and Refutation versus Derandomization for Arthur-Merlin Protocols"],"prefix":"10.1007","volume":"34","author":[{"given":"Dieter","family":"van Melkebeek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicollas","family":"Mocelin Sdroievski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,23]]},"reference":[{"key":"279_CR1","doi-asserted-by":"crossref","unstructured":"Bar\u0131\u015f Ayd\u0131nl\u0131o\u011flu & Dieter van Melkebeek (2017). Nondeterministic\nCircuit Lower Bounds from Mildly Derandomizing Arthur\u2013\nMerlin Games. Computational Complexity 26(1), 79\u2013118. ISSN 1420-\n8954. URL https:\/\/doi.org\/10.1007\/s00037-014-0095-y.","DOI":"10.1007\/s00037-014-0095-y"},{"key":"279_CR2","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, Noam Nisan & Avi Wigderson\n(1993). BPP has subexponential-time simulations unless EXPTIME\nhas Publishable Proofs. Computational Complexity 3(4), 307\u2013318. ISSN\n1420-8954. URL https:\/\/doi.org\/10.1007\/BF01275486.","DOI":"10.1007\/BF01275486"},{"key":"279_CR3","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai & Shlomo Moran (1988). Arthur\u2013Merlin Games: A\nRandomized Proof System, and a Hierarchy of Complexity Classes.\nJournal of Computer and System Sciences 36(2), 254\u2013276. ISSN 0022-\n0000.","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"279_CR4","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan & S. Vadhan\n(2005). Short PCPs verifiable in polylogarithmic time. In Conference\non Computational Complexity (CCC), 120\u2013134.","DOI":"10.1109\/CCC.2005.27"},{"key":"279_CR5","doi-asserted-by":"crossref","unstructured":"Venkatesan T. Chakaravarthy & Sambuddha Roy (2011).\nArthur and Merlin as Oracles. Computational Complexity 20(3),\n505\u2013558. ISSN 1420-8954. URL https:\/\/doi.org\/10.1007\/s00037-011-0015-3.","DOI":"10.1007\/s00037-011-0015-3"},{"key":"279_CR6","doi-asserted-by":"crossref","unstructured":"L. Chen, R. D. Rothblum & R. Tell (2022). Unstructured Hardness\nto Average-Case Randomness. In Symposium on Foundations of\nComputer Science (FOCS), 429\u2013437.","DOI":"10.1109\/FOCS54457.2022.00048"},{"key":"279_CR7","doi-asserted-by":"crossref","unstructured":"Lijie Chen, Ron D. Rothblum, Roei Tell & Eylon Yogev\n(2020). On Exponential-Time Hypotheses, Derandomization, and Circuit\nLower Bounds: Extended Abstract. In Symposium on Foundations\nof Computer Science (FOCS), 13\u201323.","DOI":"10.1109\/FOCS46700.2020.00010"},{"key":"279_CR8","doi-asserted-by":"crossref","unstructured":"Lijie Chen & Roei Tell (2021). Hardness vs Randomness, Revised:\nUniform, Non-Black-Box, and Instance-Wise. In Symposium on Foundations\nof Computer Science (FOCS), 125\u2013136.","DOI":"10.1109\/FOCS52979.2021.00021"},{"key":"279_CR9","doi-asserted-by":"crossref","unstructured":"Lijie Chen, Roei Tell & Ryan Williams (2023). Derandomization\nvs Refutation: A Unified Framework for Characterizing Derandomization.\nIn Symposium on Foundations of Computer Science (FOCS),\n1008\u20131047.","DOI":"10.1109\/FOCS57990.2023.00062"},{"key":"279_CR10","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2011). In a World of P=BPP. In Studies in Complexity\nand Cryptography. Miscellanea on the Interplay between Randomness\nand Computation, 191\u2013232. Springer. ISBN 978-3-642-22670-0.\nURL https:\/\/doi.org\/10.1007\/978-3-642-22670-0_20. Part of the\nLecture Notes in Computer Science book series (LNCS, volume 6650).","DOI":"10.1007\/978-3-642-22670-0_20"},{"key":"279_CR11","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2018). On Doubly-Efficient Interactive Proof Systems.\nFoundations and Trends in Theoretical Computer Science 13,\n157\u2013246.","DOI":"10.1561\/0400000084"},{"key":"279_CR12","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2020). Two Comments on Targeted Canonical\nDerandomizers. In Computational Complexity and Property Testing:\nOn the Interplay Between Randomness and Computation, 24\u201335.\nSpringer. ISBN 978-3-030-43662-9. URL https:\/\/doi.org\/10.1007\/978-3-030-43662-9_4.","DOI":"10.1007\/978-3-030-43662-9_4"},{"key":"279_CR13","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser, Yael Tauman Kalai & Guy N. Rothblum\n(2015). Delegating Computation: Interactive Proofs for Muggles. Journal\nof the ACM 62(4). ISSN 0004-5411. URL https:\/\/doi.org\/10.1145\/2699436.","DOI":"10.1145\/2699436"},{"key":"279_CR14","doi-asserted-by":"crossref","unstructured":"Dan Gutfreund, Ronen Shaltiel & Amnon Ta-Shma (2003).\nUniform Hardness Versus Randomness Trade-offs for Arthur\u2013Merlin\nGames. Computational Complexity 12(3), 85\u2013130. ISSN 1420-8954.\nURL https:\/\/doi.org\/10.1007\/s00037-003-0178-7.","DOI":"10.1007\/s00037-003-0178-7"},{"key":"279_CR15","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Valentine Kabanets & Avi Wigderson\n(2002). In Search of an Easy Witness: Exponential Time vs. Probabilistic\nPolynomial Time. Journal of Computer and System Sciences\n65(4), 672 \u2013 694. ISSN 0022-0000.","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"279_CR16","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). P = BPP if E Requires\nExponential Circuits: Derandomizing the XOR Lemma. In Symposium\non Theory of Computing (STOC), 220\u2013229. ISBN 0897918886.\nURL https:\/\/doi.org\/10.1145\/258533.258590.","DOI":"10.1145\/258533.258590"},{"key":"279_CR17","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Avi Wigderson (2001). Randomness vs\nTime: Derandomization under a Uniform Assumption. Journal of Computer\nand System Sciences 63(4), 672\u2013688. ISSN 0022-0000.","DOI":"10.1006\/jcss.2001.1780"},{"key":"279_CR18","doi-asserted-by":"crossref","unstructured":"J. Justesen (1976). On the complexity of decoding Reed-Solomon\ncodes (Corresp.). IEEE Transactions on Information Theory 22(2),\n237\u2013238.","DOI":"10.1109\/TIT.1976.1055516"},{"key":"279_CR19","doi-asserted-by":"crossref","unstructured":"Adam R. Klivans & Dieter van Melkebeek (2002). Graph Nonisomorphism\nhas Subexponential Size Proofs Unless the Polynomial-Time\nHierarchy Collapses. SIAM Journal on Computing 31(5), 1501\u20131526.","DOI":"10.1137\/S0097539700389652"},{"key":"279_CR20","unstructured":"Oliver Korten (2022). Derandomization from Time-Space Tradeoffs.\nIn Computational Complexity Conference (CCC), 37:1\u201337:26. ISBN\n978-3-95977-241-9. ISSN 1868-8969."},{"key":"279_CR21","unstructured":"Yanyi Liu & Rafael Pass (2022). Characterizing Derandomization\nThrough Hardness of Levin\u2013Kolmogorov Complexity. In Computational\nComplexity Conference (CCC), volume 234, 35:1\u201335:17. ISBN 978-3-\n95977-241-9. ISSN 1868-8969."},{"key":"279_CR22","unstructured":"Yanyi Liu & Rafael Pass (2023). Leakage-Resilient Hardness vs Randomness.\nIn Computational Complexity Conference (CCC), volume 264,\n32:1\u201332:20. ISBN 978-3-95977-282-2. ISSN 1868-8969."},{"key":"279_CR23","doi-asserted-by":"crossref","unstructured":"Chi-Jen Lu (2001). Derandomizing Arthur\u2013Merlin games under uniform\nassumptions. Computational Complexity 10(3), 247\u2013259. ISSN\n1420-8954.","DOI":"10.1007\/s00037-001-8196-9"},{"key":"279_CR24","unstructured":"Dieter van Melkebeek & Nicollas Mocelin Sdroievski (2023).\nInstance-Wise Hardness Versus Randomness Trade-offs for Arthur\u2013\nMerlin Protocols. In Computational Complexity Conference (CCC), volume\n264, 17:1\u201317:36. ISBN 978-3-95977-282-2. ISSN 1868-8969."},{"key":"279_CR25","doi-asserted-by":"crossref","unstructured":"Peter Bro Miltersen & N. V. Vinodchandran (2005). Derandomizing\nArthur\u2013Merlin Games using Hitting Sets. Computational\nComplexity 14(3), 256\u2013279. ISSN 1420-8954. URL https:\/\/doi.org\/10.1007\/s00037-005-0197-7.","DOI":"10.1007\/s00037-005-0197-7"},{"key":"279_CR26","doi-asserted-by":"crossref","unstructured":"Noam Nisan & Avi Wigderson (1994). Hardness vs Randomness.\nJournal of Computer and System Sciences 49(2), 149\u2013167. ISSN 0022-\n0000.","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"279_CR27","doi-asserted-by":"crossref","unstructured":"Ronen Shaltiel & Christopher Umans (2005). Simple Extractors\nfor All Min-Entropies and a New Pseudorandom Generator. Journal of\nthe ACM 52(2), 172\u2013216. ISSN 0004-5411.","DOI":"10.1145\/1059513.1059516"},{"key":"279_CR28","doi-asserted-by":"crossref","unstructured":"Ronen Shaltiel & Christopher Umans (2009). Low-End Uniform\nHardness versus Randomness Trade-offs for AM. SIAM Journal on\nComputing 39(3), 1006\u20131037.","DOI":"10.1137\/070698348"},{"key":"279_CR29","doi-asserted-by":"crossref","unstructured":"D.A. Spielman (1996). Linear-time encodable and decodable errorcorrecting\ncodes. IEEE Transactions on Information Theory 42(6),\n1723\u20131731.","DOI":"10.1109\/18.556668"},{"key":"279_CR30","doi-asserted-by":"crossref","unstructured":"Luca Trevisan & Salil Vadhan (2007). Pseudorandomness and\nAverage-Case Complexity via Uniform Reductions. Computational\nComplexity 16(4), 331\u2013364. ISSN 1420-8954. URL https:\/\/doi.org\/10.1007\/s00037-007-0233-x.","DOI":"10.1007\/s00037-007-0233-x"},{"key":"279_CR31","doi-asserted-by":"crossref","unstructured":"Christopher Umans (2003). Pseudorandom Generators for All Hardnesses.\nJournal of Computer and System Sciences 67(2), 419 \u2013 440.\nISSN 0022-0000.","DOI":"10.1016\/S0022-0000(03)00046-1"},{"key":"279_CR32","doi-asserted-by":"crossref","unstructured":"R. Ryan Williams (2016). Natural Proofs versus Derandomization.\nSIAM Journal on Computing 45(2), 497\u2013529.","DOI":"10.1137\/130938219"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00279-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00279-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00279-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:00:17Z","timestamp":1764781217000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00279-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,23]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["279"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00279-2","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,10,23]]},"assertion":[{"value":"12 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 October 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"15"}}