- Authors: D. van Melkebeek and N. Mocelin Sdroievski
- Reference: In Proceedings of the 43rd Conference on Foundations of Software Technology and Theoretical Computer Science, pages 29:1-29:22, 2023.
Abstract
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 Σ2-machines. Our techniques also apply to natural simulation models that are intermediate between nondeterministic machines and Σ2-machines.
