<p>There are known functions on $n$ variables where depth $n$ branching programs (as non-oblivious BDDs are usually called) require exponential size.  The book to read is <a href="http://books.google.com/books/about/Branching_programs_and_binary_decision_d.html?id=-DZjVz9E4f8C" rel="nofollow">by Wegner</a>.</p>

<p>Stronger lower bounds are given <a href="http://eccc.hpi-web.de/eccc-reports/1999/TR99-026/" rel="nofollow">by Ajtai</a>, and there is some <a href="http://scholar.google.com/scholar?cites=12236034035052283642&amp;as_sdt=2005&amp;sciodt=0,5&amp;hl=en" rel="nofollow">newer work</a>, but I'm not sure about which is best to read.</p>

CC BY-SA 3.0
2011-08-14T20:47:49.847Z
can't we get this by counting? Also, do any of these achieve separations of the sort asked in my questions. I.e. the BDD has smaller size (or width) if we allow larger depth?
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-14T21:03:22.307Z
Ahh, okay, I see the trade-off mentioned about Ajtali's result: "Ajtai shows, for certain specific functions, that any branching program using space S=o(n) requires time T that is superlinear." Thanks, I will take a closer look!
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-18T13:50:56.610Z
@Artem: note that the power of Ajtai's result (as well as previous ones for **oblivious** BDDs) lies in their explicitness: tradeoffs are shown for **explicit** functions. Interestingly, no similar tradeoff is known for **nondeterministic** BDDs: here no exponential lower bound is known even for BDDs of depth $n+1$(!) But if you are not interested in explicit tradeoffs, then (I admit) arbitrarily large tradeoffs can be obtained just by counting: depth seems to be a more sensible resource than width (cf. Barrington's result: width doesn't help much for $NC^1$ functions).
Stasys
CC BY-SA 3.0
2011-08-14T19:49:03.437Z
2011-08-14T19:49:03.437Z
Noam
<h2>Terminology</h2>
<p>A binary decision diagram is a directed acyclic graph with one source (root), and two sinks (<span class="math-container">$A$</span> and <span class="math-container">$B$</span>). Each non-sink nodes is labeled by an integer <span class="math-container">$i \in \{1,...,n\}$</span> and has out-degree 2 (one edge labeled '0', the other '1'). Visiting a node with label <span class="math-container">$i$</span> corresponds to queering the bit <span class="math-container">$x_i$</span> of the input and following the <span class="math-container">$0$</span>-edge if <span class="math-container">$x_i = 0$</span> and the <span class="math-container">$1$</span>-edge otherwise. When you arrive at a sink, you output its value <span class="math-container">$A$</span> or <span class="math-container">$B$</span> as the solution to the function represented by the BDD.</p>
<ul>
<li>The <strong>depth</strong> of a BDD is the length of the longest path from source to sink.</li>
<li>A slice at depth <span class="math-container">$k$</span> is the set of all nodes that are a distance <span class="math-container">$k$</span> from the root. The <strong>width</strong> of a BDD is the size of the largest slice.</li>
<li>The <strong>size</strong> of a BDD is the total number of nodes.</li>
</ul>
<p>A BDD is free, if there is no constraints on the labeling of the nodes. This is in contrast to the more commonly studied restriction of Ordered BDD that does not allow you to label a vertex <span class="math-container">$i \geq j$</span> if an ancestor is labeled <span class="math-container">$j$</span>.</p>
<h2>Question</h2>
<p>Given a total boolean function <span class="math-container">$f$</span> is there a trade off between the depth and width (or depth and size) of the BDDs representing it?</p>
<p>Let <span class="math-container">$D(f)$</span> be the query complexity of <span class="math-container">$f$</span>, and let BDD mean BDD representing <span class="math-container">$f$</span>. Are there cases that every BDD of depth <span class="math-container">$D(f)$</span> has a strictly larger width than a BDD of larger depth?</p>
<hr />
<h2>Motivation</h2>
<p>This question is a follow up to:</p>
<p><a href="https://cstheory.stackexchange.com/q/7413/1037">Trade off between time and query complexity</a></p>
<p>The hope is that by looking at a more rigid model such as BDDs we might be able to build intuition for that question in the interesting case of total functions. For a free BDD the depth corresponds directly to query complexity. The width is usually seen as a measure of space not time, so this question is also a restriction of <a href="https://cstheory.stackexchange.com/q/4556/1037">time-space trade offs</a>. However, the hope is that learning some trade offs between depth and width/size can help build similar things for query-vs-time in the circuit model.</p>
<p>Note that the case of partial functions is not interesting, since the Kothari-Fitzsimons construction from the previous question can be modified to give a separation for BDDs (although not an arbitrary one; at most exponential). The case of the better studied ordered BDDs is also less interesting, because it is easy to show that the depth of an ordered BDD does not correspond to query complexity. You can give examples of total functions where any ordered BDD has exponentially higher depth than the function's query complexity.</p>

<cc.complexity-theory><query-complexity><binary-decision-diagrams>
Trade off between width and depth of free BDDs for total functions
Artem Kaznatcheev
# Trade off between width and depth of free BDDs for total functions

(Asked by: username_0 on 2011-08-14)

## Terminology

A binary decision diagram is a directed acyclic graph with one source (root), and two sinks ($A$ and $B$). Each non-sink nodes is labeled by an integer $i \in \{1,...,n\}$ and has out-degree 2 (one edge labeled '0', the other '1'). Visiting a node with label $i$ corresponds to queering the bit $x\_i$ of the input and following the $0$-edge if $x\_i = 0$ and the $1$-edge otherwise. When you arrive at a sink, you output its value $A$ or $B$ as the solution to the function represented by the BDD.

* The **depth** of a BDD is the length of the longest path from source to sink.
* A slice at depth $k$ is the set of all nodes that are a distance $k$ from the root. The **width** of a BDD is the size of the largest slice.
* The **size** of a BDD is the total number of nodes.

A BDD is free, if there is no constraints on the labeling of the nodes. This is in contrast to the more commonly studied restriction of Ordered BDD that does not allow you to label a vertex $i \geq j$ if an ancestor is labeled $j$.

## Question

Given a total boolean function $f$ is there a trade off between the depth and width (or depth and size) of the BDDs representing it?

Let $D(f)$ be the query complexity of $f$, and let BDD mean BDD representing $f$. Are there cases that every BDD of depth $D(f)$ has a strictly larger width than a BDD of larger depth?

---

## Motivation

This question is a follow up to:

[Trade off between time and query complexity](https://cstheory.stackexchange.com/q/7413/1037)

The hope is that by looking at a more rigid model such as BDDs we might be able to build intuition for that question in the interesting case of total functions. For a free BDD the depth corresponds directly to query complexity. The width is usually seen as a measure of space not time, so this question is also a restriction of [time-space trade offs](https://cstheory.stackexchange.com/q/4556/1037). However, the hope is that learning some trade offs between depth and width/size can help build similar things for query-vs-time in the circuit model.

Note that the case of partial functions is not interesting, since the Kothari-Fitzsimons construction from the previous question can be modified to give a separation for BDDs (although not an arbitrary one; at most exponential). The case of the better studied ordered BDDs is also less interesting, because it is easy to show that the depth of an ordered BDD does not correspond to query complexity. You can give examples of total functions where any ordered BDD has exponentially higher depth than the function's query complexity.

**Tags:** cc.complexity-theory, query-complexity, binary-decision-diagrams


---

## 1 answers

### Answer by username_1 on 2011-08-14. Score: 7 | Accepted answer

There are known functions on $n$ variables where depth $n$ branching programs (as non-oblivious BDDs are usually called) require exponential size. The book to read is [by Wegner](http://books.google.com/books/about/Branching_programs_and_binary_decision_d.html?id=-DZjVz9E4f8C).

Stronger lower bounds are given [by Ajtai](http://eccc.hpi-web.de/eccc-reports/1999/TR99-026/), and there is some [newer work](http://scholar.google.com/scholar?cites=12236034035052283642&as_sdt=2005&sciodt=0,5&hl=en), but I'm not sure about which is best to read.

> **Comments:**
> **username_0**: can't we get this by counting? Also, do any of these achieve separations of the sort asked in my questions. I.e. the BDD has smaller size (or width) if we allow larger depth?  
> **username_0**: Ahh, okay, I see the trade-off mentioned about Ajtali's result: "Ajtai shows, for certain specific functions, that any branching program using space S=o(n) requires time T that is superlinear." Thanks, I will take a closer look!  
> **username_2**: @Artem: note that the power of Ajtai's result (as well as previous ones for **oblivious** BDDs) lies in their explicitness: tradeoffs are shown for **explicit** functions. Interestingly, no similar tradeoff is known for **nondeterministic** BDDs: here no exponential lower bound is known even for BDDs of depth $n+1$(!) But if you are not interested in explicit tradeoffs, then (I admit) arbitrarily large tradeoffs can be obtained just by counting: depth seems to be a more sensible resource than width (cf. Barrington's result: width doesn't help much for $NC^1$ functions).  

---

