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

Report ID:

TR-531-96

Authors:

Date:

September 1996

Pages:

9

Download Formats:

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