A Lower Bound for Randomized Read-k-Times Branching Programs
Martin Sauerhoff · 1997
In this paper, we are concerned with randomized OBDDs and randomized read-ktimes branching programs. We present an example of a Boolean function which has polynomial size randomized OBDDs with small, one-sided error, but only nondeterministic 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. 1 Introduction Branching programs are a theoretically and practically interesting data structure for the representation of Boolean functions. In complexity theory, among other problems, lower bounds for the size of branching programs for explicitly defined functions and the relations of the various branching program models are investigated. A branching program (BP) on the variable set fx 1 ; : : : ; x n g is a directed acyclic graph with one sour...