Abstract:
We show that if Arthur-Merlin protocols can be derandomized, then there is a language computable in deterministic exponential-time with access to an NP oracle, that requires circuits of exponential size. More formally, if every promise problem in prAM, the class of promise problems that have Arthur-Merlin protocols, can be computed by a deterministic polynomial-time algorithm with access to an NP oracle then there is a language in E^NP that requires circuits of size Ω(2ⁿ/n). The lower bound in the conclusion of our theorem suffices to construct pseudorandom generators with exponential stretch.

We also show that the same conclusion holds if the following two related problems can be computed in polynomial time with access to an NP-oracle:

1. approximately counting the number of accepted inputs of a circuit, up to multiplicative factors; and
2. recognizing an approximate lower bound on the number of accepted inputs of a circuit, up to multiplicative factors.

Journal Version:

• Computational Complexity, 20(2):329-366, 2011.
  [DOI | PDF]
  

• Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek. A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. Technical Report TR10-174, Electronic Colloquium on Computational Complexity, 2010.
  [PDF]