<p>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 <strong><em>E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997</em></strong>).</p>

<p>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 <a href="http://portal.acm.org/citation.cfm?id=1276922">here</a>). 
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.</p>

CC BY-SA 2.5
2010-09-02T10:07:37.510Z
Ah, so you divide the inputs of $f$ into two parts $f(x_1,\dots,x_k,y_1,\dots,y_l)$. Then, Alice simply follows the branches of the BDD on her input $\vec x$ and communicates her final node to Bob, who completes the calculation with $\vec y$. Since the width is $w$, she needs at most $\log w$ bits to communicate her node. Nice! This is somewhat related to the "block diagram" answer by Radu, since the existence of such a block diagram certainly implies a small communication complexity. (However, the converse "small communication complexity => small width" does not necessarily hold, does it?)
Heinrich Apfelmus
CC BY-SA 2.5
2010-09-02T10:09:51.300Z
Minor request: do you know of a version of your [linked paper](http://portal.acm.org/citation.cfm?id=1276922) that is freely available, i.e. not behind a paywall?
Heinrich Apfelmus
CC BY-SA 2.5
2010-09-02T10:38:56.513Z
Sure, here is a link : http://sylvain.berbiqui.org/llmpr-full.pdf
Sylvain Peyronnet
CC BY-SA 2.5
2010-09-02T15:42:14.427Z
"(However, the converse "small communication complexity => small width" does not necessarily hold, does it?)"
Indeed, it does not necessarily hold.
Sylvain Peyronnet
CC BY-SA 2.5
2010-08-29T21:26:16.187Z
2010-08-29T21:26:16.187Z
Sylvain Peyronnet
<p>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 <a href="http://www-cs-faculty.stanford.edu/~uno/fasc1b.ps.gz">TAoCP 4 fascicle 1</a> 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}$).</p>

<p>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.</p>

<p>(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.)</p>

<p>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 <em>tends</em> 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.</p>

CC BY-SA 2.5
2010-09-02T09:39:55.717Z
I like this criterion of $f$ being made up of blocks $b_i$. Thanks for the link to Knuth's fascicle!
Heinrich Apfelmus
CC BY-SA 2.5
2010-08-31T15:18:59.860Z
2010-08-31T17:01:05.747Z
2010-08-31T17:01:05.747Z
Radu GRIGore
<p>For calculating numbers, you should look at MTBDDs (Multi Terminal BDDs) a data structure used for (probabilistic) model checking. See for instance 
<strong><em>Representations of Discrete Functions, Sasao, Tsutomu; Fujita, Masahira (Eds.), Springer, 1996</em></strong>, the chapter 4, by Clarke <em>et al.</em> is about MTBDDs and Hybrid Decision Diagram.</p>

CC BY-SA 2.5
2010-08-29T12:53:00.870Z
2010-08-29T12:53:00.870Z
Sylvain Peyronnet
<p>In <a href="http://www-cs-faculty.stanford.edu/~uno/fasc1b.ps.gz" rel="nofollow">TAoCP 4 fascicle 1</a>, Knuth also mentions that</p>

<ul>
<li>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.</li>
<li>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</li>
</ul>

<p>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)$.</p>

CC BY-SA 2.5
2010-09-12T17:05:17.463Z
There's also a part about 'nasty' functions.
Radu GRIGore
CC BY-SA 2.5
2010-09-12T16:49:49.367Z
2010-09-12T16:49:49.367Z
Heinrich Apfelmus
<p><a href="http://en.wikipedia.org/wiki/Binary_decision_diagram">Reduced Ordered Binary Decision Diagrams</a> (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 <em>how</em> efficient they are.</p>

<p>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.</p>

<blockquote>
  <p>Is there an analogous intuition for estimating how efficiently ROBDDs can represent a given boolean formula?</p>
</blockquote>

<p>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?</p>

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

<ds.data-structures><binary-decision-diagrams>
Heuristics for estimating the efficiency of Reduced Ordered Binary Decision Diagrams?
Heinrich Apfelmus
# Heuristics for estimating the efficiency of Reduced Ordered Binary Decision Diagrams?

(Asked by: username_0 on 2010-08-29)

[Reduced Ordered Binary Decision Diagrams](http://en.wikipedia.org/wiki/Binary_decision_diagram) (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.)

**Tags:** ds.data-structures, binary-decision-diagrams

---

## 4 answers

### Answer by username_1 on 2010-08-29. Score: 7

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](http://portal.acm.org/citation.cfm?id=1276922)).
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.

> **Comments:**
> **username_0**: Ah, so you divide the inputs of $f$ into two parts $f(x_1,\dots,x_k,y_1,\dots,y_l)$. Then, Alice simply follows the branches of the BDD on her input $\vec x$ and communicates her final node to Bob, who completes the calculation with $\vec y$. Since the width is $w$, she needs at most $\log w$ bits to communicate her node. Nice! This is somewhat related to the "block diagram" answer by Radu, since the existence of such a block diagram certainly implies a small communication complexity. (However, the converse "small communication complexity => small width" does not necessarily hold, does it?)  
> **username_0**: Minor request: do you know of a version of your [linked paper](http://portal.acm.org/citation.cfm?id=1276922) that is freely available, i.e. not behind a paywall?  
> **username_1**: Sure, here is a link : http://sylvain.berbiqui.org/llmpr-full.pdf  
> **username_1**: "(However, the converse "small communication complexity => small width" does not necessarily hold, does it?)" Indeed, it does not necessarily hold.  

---

### Answer by username_2 on 2010-08-31. Score: 6

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](http://www-cs-faculty.stanford.edu/~uno/fasc1b.ps.gz) 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.

> **Comments:**
> **username_0**: I like this criterion of $f$ being made up of blocks $b_i$. Thanks for the link to Knuth's fascicle!  

---

### Answer by username_1 on 2010-08-29. Score: 2

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 by username_0 on 2010-09-12. Score: 2

In [TAoCP 4 fascicle 1](http://www-cs-faculty.stanford.edu/~uno/fasc1b.ps.gz), 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)$.

> **Comments:**
> **username_2**: There's also a part about 'nasty' functions.  

---

