Lower Bounds for Swapping Arthur and Merlin

DOI10.1007/978-3-540-74208-1_33MaRDI QIDQ3603486zbMATH OpenOpenAlexFDO

Authors Scott Diehl

Publication date 17 February 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74208-1_33

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)

Recommendations

• Quadratic simulations of Merlin-Arthur games
• Quadratic simulations of Merlin-Arthur games
• scientific article; zbMATH DE number 4050983
• Relativized Arthur-Merlin versus Merlin-Arthur games
• Arthur-Merlin games in Boolean decision trees

Cited in

(6)

• Arthur-Merlin games in Boolean decision trees
• Circuit lower bounds for Merlin-Arthur classes
• Communication complexity of set-disjointness for all probabilities
• Relativized Arthur-Merlin versus Merlin-Arthur games
• Quadratic simulations of Merlin-Arthur games
• Quadratic simulations of Merlin-Arthur games

This page was built for publication: Lower Bounds for Swapping Arthur and Merlin

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