Uniform hardness versus randomness tradeoffs for Arthur-Merlin games

DOI10.1007/s00037-003-0178-7zbMath1085.68055OpenAlexW3165549676WikidataQ62398486 ScholiaQ62398486MaRDI QIDQ1762663

Amnon Ta-Shma, Dan Gutfreund, Ronen Shaltiel

Publication date: 11 February 2005

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-003-0178-7

zbMATH Keywords

DerandomizationArthur-Merlin games

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Reconstructive dispersers and hitting set generators ⋮ (Nondeterministic) hardness vs. non-malleability ⋮ Statistically sender-private OT from LPN and derandomization ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Relations between average-case and worst-case complexity ⋮ Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ The communication complexity of private simultaneous messages, revisited ⋮ Natural Proofs versus Derandomization ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle

This page was built for publication: Uniform hardness versus randomness tradeoffs for Arthur-Merlin games