Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-174 | 12th November 2010 23:03

A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games



We present an alternate proof of the recent result by Gutfreund and Kawachi that derandomizing Arthur-Merlin games into $P^{NP}$ implies linear-exponential circuit lower bounds for $E^{NP}$. Our proof is simpler and yields stronger results. In particular, consider the promise-$AM$ problem of distinguishing between the case where a given Boolean circuit $C$ accepts at least a given number $b$ of inputs, and the case where $C$ accepts less than $\delta \cdot b$ inputs for some positive constant $\delta$. If $P^{NP}$ contains a solution for this promise problem then $E^{NP}$ requires circuits of size $\Omega(2^n/n)$ almost everywhere.

ISSN 1433-8092 | Imprint