- 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 PNP
implies linear-exponential circuit lower bounds for ENP. 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 PNP contains
a solution for this promise problem then ENP requires circuits
of size Ω(2n/n) almost everywhere.
