Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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