When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems

What is the actual cost of derandomization? And can we get it for free? These questions were recently raised by Doron et. al (FOCS 2020) and have been attracting considerable interest. In this work we extend the study of these questions to the setting of derandomizing interactive proofs systems.

First, we show conditional derandomization of MA and of AM with optimal runtime overhead, where optimality is under the #NSETH assumption. Specifically, denote by AMT IME [⇌c] [T] a protocol with c turns of interaction in which the verifier runs in polynomial time T. We prove that for every ϵ > 0 there exists δ > 0 such that: