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

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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

(8)

• Relativized Arthur-Merlin versus Merlin-Arthur games
• Arthur-Merlin games in Boolean decision trees
• Quadratic simulations of Merlin-Arthur games
• Communication complexity of set-disjointness for all probabilities
• Circuit lower bounds for Merlin-Arthur classes
• scientific article; zbMATH DE number 1335880 (Why is no real title available?)
• Quadratic simulations of Merlin-Arthur games
• Time-space lower bounds for simulating proof systems with quantum and randomized verifiers

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)