CaltechAUTHORS
  A Caltech Library Service

Low-end uniform hardness vs. randomness tradeoffs for AM

Shaltiel, Ronen and Umans, Christopher (2007) Low-end uniform hardness vs. randomness tradeoffs for AM. In: STOC '07 Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. ACM , New York, NY, pp. 430-439. ISBN 978-1-59593-631-8. https://resolver.caltech.edu/CaltechAUTHORS:20161219-151217993

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161219-151217993

Abstract

In 1998, Impagliazzo and Wigderson [18] proved a hardness vs. randomness tradeoff for BPP in the uniform setting,which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions by Trevisan and Vadhan [29] (in a slightly weaker setting). In 2003, Gutfreund,Shaltiel and Ta-Shma [11] proved a uniform hardness vs. randomness tradeoff for AM, but that result only worked on the "high-end" of possible hardness assumptions. In this work, we give uniform hardness vs. randomness tradeoffs for AM that are near-optimal for the full range of possible hardness assumptions. Following [11], we do this by constructing a hitting-set-generator (HSG) for AM with "resilient reconstruction." Our construction is a recursive variant of the Miltersen-Vinodchandran HSG [24], the only known HSG construction with this required property. The main new idea is to have the reconstruction procedure operate implicitly and locally on superpolynomially large objects, using tools from PCPs(low-degree testing, self-correction) together with a novel use of extractors that are built from Reed-Muller codes [28, 26] for a sort of locally-computable error-reduction. As a consequence we obtain gap theorems for AM (and AM ∩ coAM) that state, roughly, that either AM (or AM ∩ coAM)protocols running in time t(n) can simulate all of EXP("Arthur-Merlin games are powerful"), or else all of AM (or AM ∩ coAM) can be simulated in nondeterministic time s(n) ("Arthur-Merlin games can be derandomized"), for a near-optimal relationship between t(n) and s(n). As in GST, the case of AM ∩ coAM yields a particularly clean theorem that is of special interest due to the wide array of cryptographic and other problems that lie in this class.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/1250790.1250854DOIArticle
http://dl.acm.org/citation.cfm?doid=1250790.1250854PublisherArticle
Additional Information:© 2007 ACM. Supported by BSF grant 2004329. Supported by NSF CCF-0346991, BSF 2004329, a Sloan Research Fellowship, and an Okawa Foundation research grant.
Funders:
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2004329
NSFCCF-0346991
Alfred P. Sloan FoundationUNSPECIFIED
Okawa FoundationUNSPECIFIED
Subject Keywords:Theory, Algorithms, Arthur-Merlin games, hardness vs. randomness tradeoff, derandomization, hitting-set generator
Classification Code:F.2.3 [Theory of Computation]: Tradeoffs Between Complexity Measures
DOI:10.1145/1250790.1250854
Record Number:CaltechAUTHORS:20161219-151217993
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20161219-151217993
Official Citation:Ronen Shaltiel and Christopher Umans. 2007. Low-end uniform hardness vs. randomness tradeoffs for AM. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (STOC '07). ACM, New York, NY, USA, 430-439. DOI=http://dx.doi.org/10.1145/1250790.1250854
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:72944
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:20 Dec 2016 00:18
Last Modified:11 Nov 2021 05:09

Repository Staff Only: item control page