Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games

Hardness against nondeterministic circuits is known to suffice for derandomizing Arthur-Merlin games. We show a result in the other direction - that hardness against nondeterministic circuits is *necessary* for derandomizing Arthur-Merlin games. In fact, we obtain an equivalence for a mild notion of derandomization: Arthur-Merlin games can be simulated in Σ₂SUBEXP (the sub exponential version of Σ₂P) with sub polynomial advice on infinitely many input lengths if and only if Σ₂E (the linear-exponential version of Σ₂P) requires nondeterministic circuits of super polynomial size on infinitely many input lengths. Our equivalence result represents a full analogue of a similar result by Impagliazzo et al. in the deterministic setting: Randomized polynomial-time decision procedures can be simulated in NSUBEXP (the sub exponential version of NP) with sub polynomial advice on infinitely many input lengths if and only if NE (the linear-exponential version of NP) requires deterministic circuits of super polynomial size on infinitely many input lengths. A key ingredient in our proofs is improved Karp-Lipton style collapse results for nondeterministic circuits. The following are two instantiations that may be of independent interest: Assuming that Arthur-Merlin games can be derandomized in Σ₂P, we show that (i) PSPACE ⊆ NP/poly implies PSPACE ⊆ Σ₂P, and (ii) coNP ⊆ NP/poly implies PH ⊆ P^Σ₂^P.