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


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.