Derandomizing Arthur-Merlin games under uniform assumptions
DOI10.1007/S00037-001-8196-9zbMATH Open0993.68038OpenAlexW2082571280MaRDI QIDQ1601037FDOQ1601037
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
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
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)
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
- Pseudo-random generators for all hardnesses
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- 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
- Title not available (Why is that?)
- New Computational Paradigms
- A zero-one law for RP and derandomization of AM if NP is not small
- 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)
