scientific article; zbMATH DE number 1335880

MaRDI QIDQ4258571zbMATH OpenFDO

Authors Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai Vereshagin

Publication date 17 October 2000

zbMATH Keywords

Arthur-Merlin gamesprobabilistic Boolean decision trees

Mathematics Subject Classification ID

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

Recommendations

• Arthur-Merlin games in Boolean decision trees
• scientific article; zbMATH DE number 4050983
• Relativized Arthur-Merlin versus Merlin-Arthur games
• Lower Bounds for Swapping Arthur and Merlin

Cited in

(9)

• The layer complexity of Arthur-Merlin-like communication
• Derandomizing Arthur-Merlin games using hitting sets
• Arthur-Merlin games in Boolean decision trees
• A hierarchy theorem for interactive proofs of proximity
• An exponential separation between MA and AM proofs of proximity
• Relativized Arthur-Merlin versus Merlin-Arthur games
• New Computational Paradigms
• scientific article; zbMATH DE number 4050983 (Why is no real title available?)
• Zero-information protocols and unambiguity in Arthur-Merlin communication (extended abtract)

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