Low-End Uniform Hardness versus Randomness Tradeoffs for AM

DOI10.1137/070698348zbMath1194.68120OpenAlexW2029767661MaRDI QIDQ3575157

Ronen Shaltiel, Christopher Umans

Publication date: 7 July 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://resolver.caltech.edu/CaltechAUTHORS:20091023-111539349

zbMATH Keywords

derandomizationArthur-Merlin gameshardness versus randomnesshitting-set generator

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ (Nondeterministic) hardness vs. non-malleability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A PCP Characterization of AM ⋮ In a World of P=BPP

This page was built for publication: Low-End Uniform Hardness versus Randomness Tradeoffs for AM