Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-038 | 9th July 1998 00:00

On the Computational Power of Randomized Branching Programs

RSS-Feed

Abstract:

We survey some upper and lower bounds established recently on
the sizes of randomized branching programs computing explicit
boolean functions. In particular, we display boolean
functions on which randomized read-once ordered branching
programs are exponentially more powerful than deterministic
or nondeterministic read-$k$-times branching programs for any
$k=o(n/\!\log n)$. We investigate further computational
power of randomized read-once order branching programs
(OBDDs) and their basic manipulation properties for
verification of boolean functions and for testing graphs of
arithmetic functions.



ISSN 1433-8092 | Imprint