Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2, 2009 | Published
Journal Article Open

Low-End Uniform Hardness versus Randomness Tradeoffs for AM

Abstract

Impagliazzo and Wigderson [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 1998, pp. 734–743] proved a hardness versus randomness tradeoff for BPP in the uniform setting, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions (in slightly weaker settings). Gutfreund, Shaltiel, and Ta-Shma [Comput. Complexity, 12 (2003), pp. 85–130] proved a uniform hardness versus randomness tradeoff for AM, but that result worked only on the "high end" of possible hardness assumptions. In this work, we give uniform hardness versus randomness tradeoffs for AM that are near-optimal for the full range of possible hardness assumptions. Following Gutfreund, Shaltiel, and Ta-Shma, 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 [Comput. Complexity, 14 (2005), pp. 256–279], 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 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 Gutfreund, Shatiel, and Ta-Shma, 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.

Additional Information

© 2009 SIAM. Received August 1, 2007; accepted May 15, 2008; published September 2, 2009. This research was supported by BSF grant 2004329 and ISF grant 686/07. The research of this author was supported by NSF grant CCF-0346991, BSF grant 2004329, an Alfred P. Sloan Research Fellowship, and an Okawa Foundation research grant. We are grateful to Amnon Ta-Shma for helpful conversations and to the anonymous referees for their useful comments.

Attached Files

Published - Shaltiel2009p6016Siam_J_Comput.pdf

Files

Shaltiel2009p6016Siam_J_Comput.pdf
Files (419.5 kB)
Name Size Download all
md5:c48bb364454a75267d191f22e3c8a1f0
419.5 kB Preview Download

Additional details

Created:
August 21, 2023
Modified:
October 19, 2023