We extend the tools for proving lower bounds for randomized branching
programs by presenting a new technique for the read-once case which is
applicable to a large class of functions. This technique fills the gap
between simple methods only applicable for OBDDs and the well-known
"rectangle technique" of Borodin, Razborov and Smolensky which works
for the quite general models of nondeterministic and randomized
read-k-times branching programs, but which has the drawback that it
could only be applied to very special functions so far.
By an application of this technique, we resolve the remaining open
problems concerning the relations of the most important probabilistic
complexity classes for read-once branchings programs. We obtain that
the analogues of the classes BPP and NP for read-once branching
programs are incomparable and that RP is a proper subclass of NP.
The proof of Theorem 1 in the paper contains an error and the presented
technique for proving lower bounds on the size of randomized read-once
branching programs does not work.
We show that one of the functions considered in the paper, the
"addressing function" of Jukna, is computable in polynomial size by a
randomized read-once branching program with zero error.
