Lower Bounds for Swapping Arthur and Merlin

DOI10.1007/978-3-540-74208-1_33zbMATH Open1171.68487OpenAlexW111399865MaRDI QIDQ3603486FDOQ3603486

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

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

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)

Cited In (6)

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

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)