Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with CommunicationComplexity:
TR97-019 | 5th May 1997
Martin Sauerhoff

A Lower Bound for Randomized Read-k-Times Branching Programs

In this paper, we are concerned with randomized OBDDs and randomized
read-k-times branching programs. We present an example of a Boolean
function which has polynomial size randomized OBDDs with small,
one-sided error, but only non-deterministic read-once branching
programs of exponential size. Furthermore, we discuss a lower bound
technique for randomized ... more >>>

ISSN 1433-8092 | Imprint