ECCC-Report TR95-054https://eccc.weizmann.ac.il/report/1995/054Comments and Revisions published for TR95-054en-usMon, 27 Nov 1995 10:42:36 +0200
Paper TR95-054
| On the Power of Randomized Branching Programs |
Farid Ablayev,
Marek Karpinski
https://eccc.weizmann.ac.il/report/1995/054 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)$).
Mon, 27 Nov 1995 10:42:36 +0200https://eccc.weizmann.ac.il/report/1995/054