2026-07-23T22:37:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19402 2024-03-06T11:03:57Z ddc:004 open_access

Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols van Melkebeek, Dieter Mocelin Sdroievski, Nicollas Hardness versus randomness tradeoff leakage resilience Arthur-Merlin protocol targeted hitting set generator Many derandomization results for probabilistic decision processes have been ported to the setting of Arthur-Merlin protocols. Whereas the ultimate goal in the first setting consists of efficient simulations on deterministic machines (BPP vs. P problem), in the second setting it is efficient simulations on nondeterministic machines (AM vs. NP problem). Two notable exceptions that have not yet been ported from the first to the second setting are the equivalence between whitebox derandomization and leakage resilience (Liu and Pass, 2023), and the equivalence between whitebox derandomization and targeted pseudorandom generators (Goldreich, 2011). We develop both equivalences for mild derandomizations of Arthur-Merlin protocols, i.e., simulations on Σ₂-machines. Our techniques also apply to natural simulation models that are intermediate between nondeterministic machines and Σ₂-machines. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dieter van Melkebeek and Nicollas Mocelin Sdroievski 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.29 urn:nbn:de:0030-drops-194024 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.29 eng https://creativecommons.org/licenses/by/4.0/legalcode