|
Published Articles >> Table of Contents >> Abstract
18th Annual IEEE Conference on Computational Complexity (CCC'03)
p. 33
Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games
Dan Gutfreund, The Hebrew University of Jerusalem, Israel, 91904
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214408
Send link to a friend
| 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.
|
 Additional Information
|
Citation:
Dan Gutfreund,
"Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games,"
complexity,
p. 33,
18th Annual IEEE Conference on Computational Complexity (CCC'03),
2003
|
|
