On the Power of Randomized Branching Programs
Report ID: TR-531-96Author: Ablayev, Farid / Karpinski, Marek
Date: 1996-10-00
Pages: 9
Download Formats: |Postscript|
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)$).