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)

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

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)