Derandomizing Arthur-Merlin games under uniform assumptions

DOI10.1007/S00037-001-8196-9MaRDI QIDQ1601037zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 2080255
• Derandomizing Arthur-Merlin games using hitting sets
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
• Derandomization in game-theoretic probability
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• New Computational Paradigms
• Arthur-Merlin games in Boolean decision trees

Cited in

(20)

• Arthur and Merlin as oracles
• scientific article; zbMATH DE number 2080255 (Why is no real title available?)
• NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
• A zero-one law for RP and derandomization of AM if NP is not small
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• Holographic Proofs and Derandomization
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Pseudorandomness for approximate counting and sampling
• Arthur and Merlin as Oracles
• Randomization, derandomization and antirandomization: Three games
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Constructive separations and their consequences
• Easiness assumptions and hardness tests: Trading time for zero error
• Pseudo-random generators for all hardnesses
• Derandomizing Arthur-Merlin games using hitting sets
• New Computational Paradigms

This page was built for publication: Derandomizing Arthur-Merlin games under uniform assumptions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1601037)