TY - GEN
T1 - Arthur-Merlin games in Boolean decision trees
AU - Raz, R.
AU - Tardos, G.
AU - Verbitsky, O.
AU - Vereshagin, N.
N1 - Publisher Copyright:
© 1998 IEEE.
PY - 1998
Y1 - 1998
N2 - It is well known that probabilistic boolean decision trees cannot be much more powerful than deterministic ones. 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 decision tree complexity is ω(n). The latter should be contrasted with another fact we prove. Namely, if a function has Merlin-Arthur complexity 1 with one-sided error probability ϵ∈(0, 2/3], then its nondeterministic complexity is bounded by a constant.
AB - It is well known that probabilistic boolean decision trees cannot be much more powerful than deterministic ones. 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 decision tree complexity is ω(n). The latter should be contrasted with another fact we prove. Namely, if a function has Merlin-Arthur complexity 1 with one-sided error probability ϵ∈(0, 2/3], then its nondeterministic complexity is bounded by a constant.
UR - http://www.scopus.com/inward/record.url?scp=85038566147&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85038566147&partnerID=8YFLogxK
U2 - 10.1109/CCC.1998.694591
DO - 10.1109/CCC.1998.694591
M3 - Conference contribution
AN - SCOPUS:85038566147
SN - 0818683953
T3 - Proceedings of the Annual IEEE Conference on Computational Complexity
SP - 58
EP - 67
BT - Proceedings - 13th Annual IEEE Conference on Computational Complexity, CCC 1998
PB - IEEE Computer Society
T2 - 13th Annual IEEE Conference on Computational Complexity, CCC 1998
Y2 - 15 June 1998 through 18 June 1998
ER -