TR95-054 Authors: Farid Ablayev, Marek Karpinski

Publication: 27th November 1995 10:42

Downloads: 2035

Keywords:

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

read-once ordered branching program with a small

one-sided error;

2) $f_{n}$ cannot be computed in polynomial size by

deterministic read-once branching programs;

3) $f_{n}$ cannot be computed in polynomial size by

deterministic read-$k$-times ordered branching program

for $k=o(n/\log n)$ (the required deterministic size is

$\exp\left(\Omega\left(\frac{n}{k}\right)\right)$).