TR10-174 Authors: Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek

Publication: 12th November 2010 23:03

Downloads: 2555

Keywords:

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.