Abstract
Impagliazzo and Wigderson proved a uniform hardness vs. randomness "gap result" for BPP. We show an analogous result for AM: Either Arthur-Merlin protocols are very strong and everything in E = DTIME (2O(n)) can be proved to a sub-exponential time verifier, or else Arthur-Merlin protocols are weak and every language in AM has a polynomial time nondeter- ministic algorithm in the uniform average-case setting (i.e., it is infeasible to come up with inputs on which the algorithm fails). For the class AM n coAM we can re- move the average-case clause and show under the same assumption that AM n coAM = NPncoNP. A new ingredient in our proof is identifying a novel resiliency property of hardness vs. randomness trade- offs. We observe that the Miltersen-Vinodchandran generator has this property.