Derandomizing Arthur-Merlin games under uniform assumptions

DOI10.1007/3-540-40996-3_26MaRDI QIDQ4472503zbMATH OpenFDO

Authors Chi-Jen Lu

Publication date 4 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/1969/19690302.htm

Mathematics Subject Classification ID

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

Recommendations

• Derandomizing Arthur-Merlin games under uniform assumptions
• 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

(11)

• Randomization, derandomization and antirandomization: Three games
• Derandomizing Arthur-Merlin games under uniform assumptions
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Holographic Proofs and Derandomization
• NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
• New Computational Paradigms
• Easiness assumptions and hardness tests: Trading time for zero error
• Derandomizing Arthur-Merlin games using hitting sets

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 Q4472503)