Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1998 Copyright 1998 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V