ECCC-Report TR12-080https://eccc.weizmann.ac.il/report/2012/080Comments and Revisions published for TR12-080en-usMon, 18 Jun 2012 18:16:51 +0300
Paper TR12-080
| Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games |
Dieter van Melkebeek,
Baris Aydinlioglu
https://eccc.weizmann.ac.il/report/2012/080In 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.Mon, 18 Jun 2012 18:16:51 +0300https://eccc.weizmann.ac.il/report/2012/080