Arthur–Merlin Games in Boolean Decision Trees
✍ Scribed by Ran Raz; Gábor Tardos; Oleg Verbitsky; Nikolai Vereshchagin
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 253 KB
- Volume
- 59
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
It is well known that probabilistic boolean decision trees cannot be much more powerful than deterministic ones (N. Nisan, SIAM J. Comput. 20, No. 6 (1991), 999 1007). Motivated by a question if randomization can significantly speed up a nondeterministic computation via a boolean decision tree, we address structural properties of Arthur Merlin games in this model and prove some lower bounds. We consider two cases of interest, the first when the length of communication between the players is limited and the second, if it is not. While in the first case we can carry over the relations between the corresponding Turing complexity classes, in the second case we observe in contrast with Turing complexity that a one-round Merlin Arthur protocol is as powerful as a general interactive proof system and, in particular, can simulate a one-round Arthur Merlin protocol. Moreover, we show that sometimes a Merlin Arthur protocol can be more efficient than an Arthur Merlin protocol and than a Merlin Arthur protocol with limited communication. This is the case for a boolean function whose set of zeroes is a code with high minimum distance and a natural uniformity condition. Such functions provide an example when the Merlin Arthur complexity is 1 with one-sided error = # ( 2 3 , 1), but at the same time the nondeterministic Article ID jcss.