Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TWO-WAY COMMUNICATION COMPLEXITY:
Reports tagged with Two-way Communication Complexity:
TR98-004 | 13th January 1998
Farid Ablayev, Marek Karpinski

#### On the Power of Randomized Ordered Branching Programs

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

ISSN 1433-8092 | Imprint