Arthur-Merlin games in Boolean decision trees

zbMath0948.68166MaRDI QIDQ1961380

Gábor Tardos, Ran Raz, Nikolai K. Vereshchagin, Oleg Verbitsky

Publication date: 22 November 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

Merlin-Arthur protocol

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Quantum certificate complexity

Cites Work

• Unnamed Item
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• Robust machines accept easy sets
• Neither reading few bits twice nor reading illegally helps much
• A general method to construct oracles realizing given relationships between complexity classes
• Selbstduale Goppa-Codes
• The Knowledge Complexity of Interactive Proof Systems
• CREW PRAM<scp>s</scp> and Decision Trees
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Arthur-Merlin games in Boolean decision trees