Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR98-004 | 13th January 1998 00:00

#### On the Power of Randomized Ordered Branching Programs

TR98-004
Authors: Farid Ablayev, Marek Karpinski
Publication: 15th January 1998 11:31
Keywords:

Abstract:

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)}$.

ISSN 1433-8092 | Imprint