- Authors: S. Aaronson, B. Aydinlioglu, H. Buhrman, J. Hitchcock, and D. van Melkebeek.

- Reference: Electronic Colloquium on Computational Complexity, Technical
Report ECCC-TR 10-174, 2010.

#### Abstract

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 *δ.b* inputs
for some positive constant *δ*. If P^{NP} contains
a solution for this promise problem then E^{NP} requires circuits
of size Ω(*2*^{n}/*n*) almost everywhere.