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