Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR10-174 | 12th November 2010 23:03

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

TR10-174
Authors: Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek
Publication: 12th November 2010 23:03
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.