2026-07-23T15:38:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18287 2024-03-06T11:01:31Z ddc:004 open_access

Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols van Melkebeek, Dieter Mocelin Sdroievski, Nicollas Hardness versus randomness tradeoff Arthur-Merlin protocol targeted hitting set generator 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 blackbox derandomization, i.e., derandomization through pseudo-random generators, has been shown equivalent to lower bounds for decision problems against circuits. Recently, Chen and Tell (FOCS'21) established near-equivalences in the BPP setting between whitebox 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 f on the given instance. In 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 f computable by a nondeterministic algorithm that runs in time n^a. We show that if every Arthur-Merlin protocol that runs in time n^c for c = O(log² a) can only compute f correctly on finitely many inputs, then AM is in NP. Our main technical contribution is the construction of suitable targeted hitting-set generators based on probabilistically checkable proofs for nondeterministic computations. As a byproduct 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). Byproducts in the average-case setting include the first uniform hardness vs. randomness tradeoffs for AM, as well as an unconditional mild derandomization result for AM. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dieter van Melkebeek and Nicollas Mocelin Sdroievski 2023 Is Part Of LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2023.17 urn:nbn:de:0030-drops-182870 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.17 eng https://creativecommons.org/licenses/by/4.0/legalcode