Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1998 Copyright 1998 Universität Bonn, Institut für Informatik, Abt. V
85194

On the Computation Power of Randomized Branching Programs
Marek Karpinski
[Download PostScript] [Download PDF]

We survey some upper and lower bounds established recently on the sizes of \emph{randomized} branching programs computing explicit boolean functions. In particular, we display boolean functions on which \emph{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 \emph{randomized} read-once order branching programs (OBDDs) and their basic manipulation properties for verification of boolean functions and for testing graphs of arithmetic functions.

Last Change: 08/18/99 at 13:00:38
 English
Universität Bonn -> Institut für Informatik -> Abteilung V