On the Power of Randomized Branching Programs

Abstract:

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