Farid Ablayev, Marek Karpinski

We define the notion of a randomized branching program in

the natural way similar to the definition of a randomized

circuit. We exhibit an explicit function $f_{n}$ for which

we prove that:

1) $f_{n}$ can be computed by polynomial size randomized

...
more >>>

Farid Ablayev, Marek Karpinski

We introduce a model of a {\em randomized branching program}

in a natural way similar to the definition of a randomized circuit.

We exhibit an explicit boolean function

$f_{n}:\{0,1\}^{n}\to\{0,1\}$ for which we prove that:

1) $f_{n}$ can be computed by a polynomial size randomized

...
more >>>

Farid Ablayev, Marek Karpinski

We prove an exponential lower bound ($2^{\Omega(n/\log n)}$) on the

size of any randomized ordered read-once branching program

computing integer multiplication. Our proof depends on proving

a new lower bound on Yao's randomized one-way communication

complexity of certain boolean functions. It generalizes to some

other ...
more >>>

Marek Karpinski

We survey some upper and lower bounds established recently on

the sizes of randomized branching programs computing explicit

boolean functions. In particular, we display boolean

functions on which randomized read-once ordered branching

programs are exponentially more powerful than deterministic

or nondeterministic read-$k$-times branching programs for ...
more >>>

Marek Karpinski, Rustam Mubarakzjanov

We prove that the error-free (Las Vegas) randomized OBDDs

are computationally equivalent to the deterministic OBDDs.

In contrast, it is known the same is not true for the

Las Vegas read-once branching programs.