Ordered binary decision diagrams and the Shannon effect (Q1878402)

The state-of-the-art data structures for Boolean functions are known as ordered binary decision diagrams (OBDDs). An OBDD is an acyclic digraph with one root and two terminals 0 and 1. This paper is devoted to theoretical investigations on the size of the OBDD of a Boolean function which has been chosen according to the uniform distribution. Using counting arguments, \textit{H. Liaw} and \textit{C. Lin} [IEEE Trans. Comput. 41, 661--664 (1992)] showed that the expected optimal OBDD size in this model is never more than a constant factor apart from the worst-case OBDD size of any function on \(n\) variables. Later \textit{I. Wegener} [IEEE Trans. Comput. 43, 1262--1269 (1994; Zbl 1068.68685)] showed that the two quantities in fact coincide up to terms of lower order, if the number of variables is uniformly distributed in \([2^{h},2^{h+1}-1]\) and \(h\) goes to infinity. The phenomenon that almost all functions have the same OBDD size as the hardest functions up to a factor of \(1+o(1)\) is called the strong Shannon effect for random Boolean functions and OBDDs. The authors show that the strong Shannon effect is not valid for all \(n\). More precisely, the strong Shannon effect does not hold within intervals of constant width around the values \(n=2^{h}+h\), where \(h\) is a natural number, but it does hold outside these intervals. Their analysis uses a large deviation inequality that follows from Azuma's martingale inequality, and Chvátal's bound on the hypergeometric distribution. This new approach proposes a generalization of OBDDs called ordered Kronecker functional decision diagrams (OKFDDs).