Many BDD (binary decision diagram) models are motivated
by CAD applications and have led to complexity theoretical
problems and results. Motivated by applications in genetic
programming Krause, Savick\'y, and Wegener (1999) have shown
that for the inner product function IP$_n$ and the direct
storage access function DSA$_n$ all functions which
approximate them on considerably more than half of the inputs
need exponential $\pi$-OBDD size for most variable orderings $\pi$.

In this paper, the results of Krause, Savick\'{y}, and Wegener
are generalized to more general BDD models like $k$-IBDDs and BP1s
(read-once branching programs). Furthermore, the size of OBDDs for
functions which approximate a function $f_n$ is compared with the
size of randomized OBDDs with two sided error for $f_n$. An exponential
gap is presented.