Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games

Authors: B. Aydinlioglu and D. van Melkebeek.
Reference: Computational Complexity, 26: 79-118, 2017.
Earlier version:
- B. Aydinlioglu and D. van Melkebeek. Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games. In Proceedings of the 27th IEEE Conference on Computational Complexity, pages 269-279, 2012.

Abstract

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 et al. implicitly showed the following equivalence: Randomized polynomial-time decision procedures can be simulated in NSUBEXP (the subexponential version of NP) with subpolynomial advice on infinitely many input lengths if and only if NEXP is not in P/poly. We establish a full analogue in the setting of verification procedures: Arthur-Merlin games can be simulated in Σ₂SUBEXP (the subexponential version of Σ₂P) with subpolynomial advice on infinitely many input lengths if and only if Σ₂EXP is not in 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 Σ₂P, we show that

if PSPACE is contained in NP/poly then PSPACE collapses to Σ₂P, and
if coNP is contained in NP/poly then PH collapses to P^Σ₂P.

dieter@cs.wisc.edu