Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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

$expleft(Omegaleft(frac{n}{k}

ight)

ight)$).

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/2

[2] http://www.cs.princeton.edu/research/techreps/author/429

[3] ftp://ftp.cs.princeton.edu/techreports/1996/531.ps.gz