Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-080 | 18th June 2012 18:15

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 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 $\not\subseteq$ P/poly. We establish a full analogue in the setting of verification procedures: Arthur-Merlin games can be simulated in $\Sigma_2$SUBEXP (the subexponential version of $\Sigma_2$P) with subpolynomial advice on infinitely many input lengths if and only if $\Sigma_2$EXP $\not\subseteq$ 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 $\Sigma_2$P, we show that
(i) PSPACE $\subseteq$ NP/poly implies PSPACE $\subseteq$ $\Sigma_2$P, and
(ii) coNP $\subseteq$ NP/poly implies PH $\subseteq$ P$^{\Sigma_2\mathrm{P}}$.

In proving our result we provide a general framework that also captures earlier conditional circuit lower bound results similar to ours.

ISSN 1433-8092 | Imprint