In this paper, we are concerned with randomized OBDDs and randomized read-k-times branching programs. We present an example of a Boolean function which has polynomial size randomized OBDDs with small, one-sided error, but only non-deterministic read-once branching programs of exponential size. Furthermore, we discuss a lower bound technique for randomized OBDDs with two-sided error and prove an exponential lower bound of this type. Our main result is an exponential lower bound for randomized read-k-times branching programs with two-sided error.
展开▼
