Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR98-038 | 9th July 1998 00:00

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

TR98-038
Authors: Marek Karpinski
Publication: 9th July 1998 12:09
Keywords:

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