TR98-004 Authors: Farid Ablayev, Marek Karpinski

Publication: 15th January 1998 11:31

Downloads: 1951

Keywords:

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

ordered read-once branching program with a small one-sided error.

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

nondeterministic ordered $read$-$k$-$times$ branching program

for any $k=o(n/\log n)$. The required nondeterministic size is

$2^{\Omega (n/k)}$.