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
... more >>>