Arthur-Merlin games in boolean decision trees

It is well known that probabilistic boolean decision trees cannot be much m ore powerful than deterministic ones (N. Nisan, SIAM J. Comput. 20, No. 6 ( 1991), 999-1007), Motivated by a question if randomization can significantl y speed up a nondeterministic computation via a boolean decision tree, we a ddress structural properties of Arthur-Merlin games in this model and prove some lower bounds. We consider two cases of interest, the first when the l ength 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 th e 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 sometim es a Merlin-Arthur protocol can be more efficient than an Arthur-Merlin pro tocol 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 mi nimum distance and a natural uniformity condition. Such functions provide a n example when the Merlin-Arthur complexity is 1 with one-sided error epsil on is an element of (2/3, 1), but at the same time the nondeterministic dec ision tree complexity is Ohm(n). The latter should be contrasted with anoth er fact we prove. Namely, if a function has Merlin-Arthur complexity 1 with one-sided error probability epsilon is an element of (0, 2/3], then its no ndeterministic complexity is bounded by a constant. Other results of the pa per include connections with the block sensitivity and related combinatoria l properties of a boolean function. (C) 1999 Academic Press.