Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games

In several settings, derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in any way implies the ability to do so in the canonical way through pseudorandom generators. For the setting of decision problems, Impagliazzo, Kabanets, and Wigderson (2002) implicitly showed the following equivalence: Randomized polynomial-time decision procedures for promise problems can be simulated in $${\sf{NSUBEXP}}$$NSUBEXP (the subexponential version of $${\sf{NP}}$$NP) with subpolynomial advice on infinitely many input lengths if and only if$${{\sf{NEXP}} \not \subseteq }$$NEXPź$${\sf{P}/ poly}$$P/poly. We establish a full analog in the setting of verification procedures: Arthur-Merlin games for promise problems can be simulated in $${{\sf{\Sigma_{2} SUBEXP}}}$$Σ2SUBEXP (the subexponential version of $${\sf{\Sigma_{2} P}}$$Σ2P) with subpolynomial advice on infinitely many input lengths if and only if$${\sf{\Sigma_2EXP} \not \subseteq }$$Σ2EXPź$${\sf{NP}/poly}$$NP/poly.

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 $${{\sf{\Sigma_{2}} P}}$$Σ2P, we show that (i) $${\sf{PSPACE} \subseteq }$$PSPACE⊆$${\sf{NP/poly}}$$NP/poly implies $${\sf{PSPACE} \subseteq \sf{\Sigma_2P}}$$PSPACE⊆Σ2P and (ii) $${\sf{coNP} \subseteq {\sf{NP/poly}}}$$coNP⊆NP/poly implies $${{\sf{PH} \subseteq \sf{P^{\Sigma_2P}}}}$$PH⊆PΣ2P.

Of possible independent interest is a generic framework that we provide, which captures several results in the literature of the form "derandomization implies circuit lower bounds." In particular, our framework enables a unified view of our result, the one by Impagliazzo et al. (2002) mentioned above, as well as the result by Kabanets and Impagliazzo (2004) that derandomizing polynomial identity testing yields arithmetic circuit lower bounds.