Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games

Aarhus, Denmark July 07-July 10

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214408

18th Annual IEEE Conference on Comput ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Dan Gutfreund

	ASCII Text	x
	Dan Gutfreund, "Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games," Computational Complexity, Annual IEEE Conference on, pp. 33, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003.

	BibTex	x
	@article{ 10.1109/CCC.2003.1214408, author = {Dan Gutfreund}, title = {Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2003}, issn = {1093-0159}, pages = {33}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214408}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games SN - 1093-0159 SP EP A1 - Dan Gutfreund, PY - 2003 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Dan Gutfreund, The Hebrew University of Jerusalem, Israel, 91904

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.

Citation:

Dan Gutfreund, "Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games," ccc, pp.33, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.