Heuristics for estimating the efficiency of Reduced Ordered Binary Decision Diagrams?

Question

Reduced Ordered Binary Decision Diagrams (ROBDD) are an efficient data structure for representing boolean functions of multiple variables $f(x_1,x_2,...,x_n)$. I would like to get an intuition for how efficient they are.

For instance, for data compression, we know that data with low entropy (some symbols appearing more often than other, many repetitions) can be compressed very well while completely random data cannot be compressed.

Is there an analogous intuition for estimating how efficiently ROBDDs can represent a given boolean formula?

For example, I have heard that multiplication of $n$-bit numbers cannot be represented efficiently, the minimum ROBDD size is exponential in $n$. Do you know of an intuitive argument that explains why this is the case?

Related question: intuition about efficiency of BDDs that calculate numbers (multiple terminal BDDs, etc.)

Answer 1

There is a relation between the width of an OBDD for a function $f$ and the communication complexity of a one-way communication protocol for the best-case partition of variables for $f$ (see E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997).

This is a powerful tool for proving exponential size OBDDs for various functions (together with coauthors, we used this method for proving that $\epsilon$-bipartiteness is hard for OBDDs, see here). Basically, if there exists an OBDD of width at most $w$ that solves $f$, then $\kappa_{best}(f) \leq \log w$. I think this is more intuitive to think in terms of communication complexity rather than OBDD.

Answer 2

One way to compute a boolean function $f(x_1,\ldots,x_n)$ is to have a chain of boolean circuit blocks $b_1,\ldots,b_n$ such that $b_k$ reads only $x_k$ (of the inputs) and is connected only to $b_{k-1}$ and $b_{k+1}$. One of the outputs of the last block $b_n$ is $f$'s value. Theorem M in TAoCP 4 fascicle 1 says that the BDD of $f$ must be big if for all such circuits you need many backward links (from $b_k$ to $b_{k-1}$).

In other words, for the BDD to be small, there must be a way to summarize the information in $x_1,\ldots,x_k$ for $1\le k\le n$. The width of the BDD corresponds to the $k$ that is hardest to compress, intuitively.

(One example given in TAoCP is this: Imagine a cycle of length $n$ and a boolean function $f(x_1,\ldots,x_n)$ that says "there is no node that has the same color as both of its neighbors," where $x_k$ says whether node $k$ is black or white. Then, the 'summary' once you looked at nodes $1,2,\ldots,k$ should store the color of $1$, $k-1$, $k$, and whether you already noticed a violation. You need $k-1$ and $k$ so that you can check whether the property is violated at $k$ once you also see $k+1$. You need $1$ so that you can check if the property is violated at $n$, once you get to the end.)

Also, if you care about operations between BDDs, then doing a binary operation between $f$ and $g$, where $f$ is represented by a BDD that has $m$ nodes and $g$ is represented by a BDD that has $n$ nodes takes $O(mn)$ time but tends to take only $O(m+n)$ time for functions you actually find in practice. I'm not aware of a precise version of what I just said, but I'd be interested if there is.

Answer 3

For calculating numbers, you should look at MTBDDs (Multi Terminal BDDs) a data structure used for (probabilistic) model checking. See for instance Representations of Discrete Functions, Sasao, Tsutomu; Fujita, Masahira (Eds.), Springer, 1996, the chapter 4, by Clarke et al. is about MTBDDs and Hybrid Decision Diagram.

Answer 4

In TAoCP 4 fascicle 1, Knuth also mentions that

• Symmetric functions $f(x_1,x_2,\dots,x_n)$ in $n$ variables have BDDs of size $\mathcal O(n^2)$. That's because $f$ can be described by a triangular diagram with just $n+1$ leaves (corresponding to the possible counts $x_1+x_2+\dots+x_n \in \lbrace 0,1,2,\dots n\rbrace$ of input variables set) instead of the full $2^n$ leaves.
• Specializing a function by setting two variables equal, like $g(x_1,x_2) := f(x_1,x_2,x_2)$ does not enlarge the BDD

This shows that functions like $f(x_1,x_2,x_3) := (2x_1 + 5x_2 + 3x_3 \ge 7)$ have efficient BDDs, since $f$ is a specialization of the symmetric function $(x_1 + x_2 + \dots + x_{10} \ge 7)$.