Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-019 | 5th May 1997 00:00

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

RSS-Feed




TR97-019
Authors: Martin Sauerhoff
Publication: 10th May 1997 11:55
Downloads: 3383
Keywords: 


Abstract:

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 OBDDs with two-sided error and prove an
exponential lower bound of this type. Our main result is an exponential
lower bound for randomized read-k-times branching programs with
two-sided error.



ISSN 1433-8092 | Imprint