TR99-011 Authors: Matthias Krause, Petr Savicky, Ingo Wegener

Publication: 14th April 1999 15:43

Downloads: 2561

Keywords:

Ordered binary decision diagrams (OBDDs) and their variants

are motivated by the need to represent Boolean functions

in applications. Research concerning these applications leads

also to problems and results interesting from theoretical

point of view. In this paper, methods from communication

complexity and information theory are combined to prove

that the direct storage access function and the inner product

function have the following property. They have linear

\pi-OBDD size for some variable ordering \pi and, for most

variable orderings \pi', all functions which approximate

them on considerably more than half of the inputs, need

exponential \pi'-OBDD size. These results have implications

for the use of OBDDs in experiments with genetic programming.