scientific article; zbMATH DE number 2080255

MaRDI QIDQ4472503zbMATH OpenFDO

Authors Chi-Jen Lu

Publication date 4 August 2004

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)

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

This page was built for publication:

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