Beate Bollig

Branching programs are a well established computation model for

Boolean functions, especially read-once branching programs have

been studied intensively.

In this paper the expressive power of nondeterministic read-once

branching programs, i.e., the class of functions

representable in polynomial size, is investigated.

For that reason two restricted models of nondeterministic read-once

more >>>

Beate Bollig, Philipp Woelfel, Stephan Waack

Branching programs are a well-established computation model

for Boolean functions, especially read-once branching programs

have been studied intensively. Exponential lower bounds for

deterministic and nondeterministic read-once branching programs

are known for a long time. On the other hand, the problem of

proving superpolynomial lower bounds ...
more >>>

Beate Bollig

Integer multiplication as one of the basic arithmetic functions has been

in the focus of several complexity theoretical investigations.

Ordered binary decision diagrams (OBDDs) are one of the most common

dynamic data structures for boolean functions.

Among the many areas of application are verification, model checking,

computer-aided design, relational algebra, ...
more >>>