Derandomizing Arthur-Merlin games under uniform assumptions

DOI10.1007/s00037-001-8196-9zbMath0993.68038OpenAlexW2082571280MaRDI QIDQ1601037

Cgi-Jen Lu

Publication date: 17 June 2002

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

Full work available at URL: https://doi.org/10.1007/s00037-001-8196-9

zbMATH Keywords

derandomization

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

In search of an easy witness: Exponential time vs. probabilistic polynomial time., A zero-one law for RP and derandomization of AM if NP is not small, Unnamed Item, NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES, Pseudo-random generators for all hardnesses