TerminologyA 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$.QuestionGiven 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? MotivationThis question is a follow up to:Trade off between time and query complexityThe 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.
Trade off between width and depth of free BDDs for total functions
cc.complexity theory;query complexity;binary decision diagrams
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.