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 ... more >>>

We obtain an exponential separation between consecutive levels in the hierarchy of classes of functions computable by polynomial-size syntactic read-$k$-times branching programs, for {\em all\/} $k>0$, as conjectured by various authors~\cite{weg87,ss93,pon95b}. For every $k$, we exhibit two explicit functions that can be computed by linear-sized read-$(\kpluso)$-times branching programs but require ... more >>>

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 ... more >>>

It is well known that every finite Abelian group $G$ can be represented as a product of cyclic groups: $G=G_1\times G_2\times\cdots G_t$, where each $G_i$ is a cyclic group of size $p^j$ for some prime $p$ and integer $j\ge 1$. If $a_i$ is the generator of the cyclic group of ... more >>>