TR97-054 Authors: Ran Raz, GĂˇbor Tardos, Oleg Verbitsky, Nikolay Vereshchagin

Publication: 21st November 1997 15:32

Downloads: 2143

Keywords:

It is well known that probabilistic boolean decision trees

cannot be much more powerful than deterministic ones (N.~Nisan, SIAM

Journal on Computing, 20(6):999--1007, 1991). 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 bounded 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

$\epsilon\in(\frac{2}{3},1)$, but at the same time the nondeterministic

decision tree complexity is $\Omega(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

$\epsilon\in(0,\frac{2}{3}]$, then its nondeterministic complexity is

bounded by a constant.

Other results of the paper include connections with the block

sensitivity and related combinatorial properties of a boolean

function.