Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games
Dan Gutfreund, Ronen Shaltiel, Amnon Ta‐Shma · 2004
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(2/sup O(n)/) can be proved to a subexponential time verifier, or else Arthur-Merlin protocols are weak and every language in AM has a polynomial time nondeterministic 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/spl cap/coAM, we can remove the average-case clause and show under the same assumption that AM/spl cap/coAM=NP/spl cap/coNP. 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.