## DIMACS TR: 96-46

## On the Power of Randomized Branching Programs

### Authors: Farid Ablayev, Marek Karpinski

**
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
$\exp\left(\Omega\left(\frac{n}{k}\right)\right)$).

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-46.ps.gz

DIMACS Home Page