Relationship between Formula Complexity and Depth Complexity of A Boolean Function

Question

A (de Morgan) formula $\phi$ is a rooted binary tree, whose leaves are identified with literals of the forms $x_i$ and $\neg x_i$, and whose internal vertices are labeled as AND ($\land$) or OR ($\lor$) gates. Here, the same literal can be associated with more than one leaf. Such a formula $\phi$ over variables $x_1,\ldots, x_n$ computes a function from $\{0, 1\}^n$ to $\{0, 1\}$ in the natural way. The size of a formula is the number of its leaves (which is the same as the number of its gates up to a factor of 2ドル$). The depth of a formula is the depth of the tree.

The formula complexity of a Boolean function $f : \{0, 1\}^n\rightarrow \{0, 1\}$, denoted $L(f)$, is the minimal size of a formula that computes $f$. The depth complexity of $f$, denoted $D(f)$, is the minimal depth of a formula that computes $f$. If $f$ is a constant function, then we define $L(f) = 0$ and $D(f) = −\infty$.

My question is how does $D(f)$ related to $L(f)$? For example, does $L(f)=2^{D(f)}$ or $L(f)\le2^{D(f)}$, etc.?

Answer 1

The relationship is $D(f)=\Theta(\log L(f))$.

On the one hand, trivially $L(f)\le2^{D(f)}$, as a binary tree of depth $d$ has size at most 2ドル^d$. On the other hand, any formula of size $s$ can be balanced to a formula of depth $O(\log s)$ by Spira’s theorem, thus $D(f)=O(\log L(f))$.