ECCC-Report TR98-004https://eccc.weizmann.ac.il/report/1998/004Comments and Revisions published for TR98-004en-usThu, 15 Jan 1998 11:31:28 +0200
Paper TR98-004
| On the Power of Randomized Ordered Branching Programs |
Farid Ablayev,
Marek Karpinski
https://eccc.weizmann.ac.il/report/1998/004 We introduce a model of a {\em randomized branching program}
in a natural way similar to the definition of a randomized circuit.
We exhibit an explicit boolean function
$f_{n}:\{0,1\}^{n}\to\{0,1\}$ for which we prove that:
1) $f_{n}$ can be computed by a polynomial size randomized
ordered read-once branching program with a small one-sided error.
2) $f_{n}$ cannot be computed in polynomial size by any
nondeterministic ordered $read$-$k$-$times$ branching program
for any $k=o(n/\log n)$. The required nondeterministic size is
$2^{\Omega (n/k)}$.
Thu, 15 Jan 1998 11:31:28 +0200https://eccc.weizmann.ac.il/report/1998/004