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.