4
$\begingroup$

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

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Stronger lower bounds are given by Ajtai, and there is some newer work, but I'm not sure about which is best to read.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Artem Kaznatcheev ♦
    Aug 14, 2011 at 20:47
  • $\begingroup$ 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! $\endgroup$
    – Artem Kaznatcheev ♦
    Aug 14, 2011 at 21:03
  • 1
    $\begingroup$ @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). $\endgroup$
    – Stasys
    Aug 18, 2011 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.