# Towards Optimal Depth-Reductions for Algebraic Formulas

Hervé Fournier  Nutan Limaye  ITU Copenhagen,
Email<EMAIL_ADDRESS>Guillaume Malod  Univ. Savoie Mont Blanc, CNRS, LAMA
Email<EMAIL_ADDRESS>Srikanth Srinivasan111The author is
grateful for a research visit sponsored by the Guest researchers faculty
program at Université Paris Cité in summer 2022. Sébastien Tavenas  Aarhus
University,
Email<EMAIL_ADDRESS>
###### Abstract

Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and
Brent (JACM 1974) show that any algebraic formula of size $s$ can be converted
to one of depth $O(\log s)$ with only a polynomial blow-up in size. In this
paper, we consider a fine-grained version of this result depending on the
degree of the polynomial computed by the algebraic formula.

Given a homogeneous algebraic formula of size $s$ computing a polynomial $P$
of degree $d$, we show that $P$ can also be computed by an (unbounded fan-in)
algebraic formula of depth $O(\log d)$ and size $\mathop{\mathrm{poly}}(s).$
Our proof shows that this result also holds in the highly restricted setting
of monotone, non-commutative algebraic formulas.

This improves on previous results in the regime when $d$ is small (i.e.,
$d=s^{o(1)}$). In particular, for the setting of $d=O(\log s),$ along with a
result of Raz (STOC 2010, JACM 2013), our result implies the same depth
reduction even for _inhomogeneous_ formulas. This is particularly interesting
in light of recent algebraic formula lower bounds, which work precisely in
this “low-degree” and “low-depth” setting.

We also show that these results cannot be improved in the monotone setting,
even for commutative formulas.

##  1 Introduction

In this paper, we study a basic question regarding computational tradeoffs
between two resources for the model of _algebraic formulas_.

An algebraic formula $F$ for a multivariate polynomial $P(x_{1},\ldots,x_{n})$
is simply an algebraic expression for $P$ made up of nested additions and
multiplications. Equivalently, it can be defined as a rooted directed tree
where the leaves are labelled by variables and internal nodes (or gates)
compute either linear combinations or products of their children (a formal
definition can be found in Section 2 below). Unless otherwise stated, we do
not bound the number of children of a gate (in other words, we consider
formulas of _unbounded fan-in_).

The two basic computational resources that describe the complexity of an
algebraic formula $F$ are its _size_ , which is the number of leaves in the
underlying tree, and its _depth_ , which naturally is the depth of the tree.
Polynomials222Strictly speaking, we should refer here to infinite sequences of
polynomials, but we ignore this distinction. that have efficient (i.e.,
$\mathop{\mathrm{poly}}(n)$-sized) algebraic formulas form the algebraic
complexity class $\mathrm{VF}.$ Like its Boolean counterpart
$\mathrm{NC}^{1}$, this is a natural and important complexity class.

Tradeoffs between size and depth in the setting of formulas and related models
of computation have been the focus of many previous works, starting from the
early 1970s [Spi71, BKM73, Bre74, VSBR83, SS80, Nis91, Raz06, RY08, AV08,
Koi12, Tav15, GKKS16, KSS14, CKSV16, LST21a]. We describe a few such results
here.

  * •

In the Boolean setting, Spira [Spi71] and independently Khrapchenko (see
[YK68]) showed that any Boolean formula of size $s$ can be converted to a
Boolean formula of depth $O(\log s)$ while keeping the size bounded by
$s^{O(1)}.$ These results were replicated in the algebraic setting in results
of Brent, Kuck and Marayuma [BKM73] and Brent [Bre74]. The constants involved
in the bounds for the depth and the size were improved in many follow-up works
[PM75, PM76, Kos86, BCE95, BB94].

  * •

This question has also been studied for the more general model of _algebraic
circuits,_ where the underlying tree is replaced by a directed acyclic graph
(DAG). A well-known result of Valiant, Skyum, Berkowitz and Rackoff [VSBR83]
showed that an algebraic circuit of size $s$ computing a polynomial of degree
$\mathop{\mathrm{poly}}(s)$ can be converted to a circuit of depth333In the
bounded fan-in case, this would be depth $O(\log^{2}s)$ instead. $O(\log s)$
and size $\mathop{\mathrm{poly}}(s)$. These results were also shown to hold
for _multilinear_ 444A circuit or formula is multilinear if each of its gates
computes a multilinear polynomial. circuits by Raz and Yehudayoff [RY08].

  * •

The above results are known to be tight in various settings. In the _monotone_
case555where the underlying field is $\mathbb{R}$ and all constants are non-
negative, so cancellations do not occur., Shamir and Snir [SS80] showed the
existence of an explicit polynomial $P$ with a
$\mathop{\mathrm{poly}}(n)$-sized circuit such that any circuit of depth
$o(\log n)$ for $P$ is of superpolynomial size. Similar results were obtained
in the multilinear case by Raz [Raz06] and Chillara, Limaye and Srinivasan
[CLS18] (for multilinear circuits and formulas, respectively).

  * •

Beginning with the work of Agrawal and Vinay [AV08], a recent line of work
[Koi12, Tav15, GKKS16, KSS14, CKSV16, KdOS19] has shown that algebraic
circuits and formulas can be converted to formulas of _constant depth_ with a
_sub-exponential_ blow-up in size. In contrast, our focus in this paper is
primarily on reducing depth as much as possible while keeping the size bounded
by $\mathop{\mathrm{poly}}(s)$, as in the results listed previously.

#### The question.

In this paper, we ask the question of whether stronger _depth-reduction_
results can be proved given a bound $d$ on the degree of the polynomial
$P(x_{1},\ldots,x_{n})$ computed by the algebraic formula. In general, an
algebraic formula of size $s$ can compute a polynomial of degree at most $s$.
When $d=s$ (or $d=s^{\Omega(1)}$), the above results imply that an algebraic
formula $F$ for $P$ can be converted to another formula $F^{\prime}$ of depth
$O(\log d)$ without significant blow-up in size. Does such a result hold for
any $d$ (or more specifically, when $d=s^{o(1)}$)?

Note that this question only makes sense for algebraic formulas of unbounded
fan-in. If the fan-in of each gate is bounded by a constant, then any formula
of size $s$ must have depth at least $\Omega(\log s)$ (and so, Brent, Kuck,
and Marayuma’s result [BKM73] is optimal). However, in many settings (see e.g.
the third motivation below), we want a finer analysis of the formula depth
that can be achieved by formulas of unbounded fan-in.

#### Motivation.

While the question is fairly natural in our opinion, there are also many
concrete reasons that lead to this line of inquiry.

  * •

It is easy to see from the proof of Valiant, Skyum, Berkowitz, and Rackoff
[VSBR83] that any algebraic _circuit_ can be depth-reduced to depth $O(\log
d)$ with only a $\mathop{\mathrm{poly}}(s,d)$ blow-up in size. So the natural
generalization for small degrees is indeed true in the setting of algebraic
circuits.

  * •

It also follows from previous results that the depth bound of $O(\log s)$ can
be improved when the degree is $d=o(\log s).$ This is due to a result of Raz
[Raz13]: any formula $F$ for a homogeneous polynomial $P$ of degree $d$ can be
converted to a _homogeneous_ formula666A homogeneous formula is one where each
gate computes a homogeneous polynomial. This means that the formula does not
compute intermediate polynomials of degree larger than $d$. $F^{\prime}$
efficiently. Further, it is easy to see that any homogeneous formula computing
a polynomial of degree $d$ has depth $O(d)=o(\log s).$ So, in this regime for
the degree, standard depth-reduction results _can_ be strengthened.

  * •

Finally, very recent results in algebraic complexity [LST21b] have suggested a
way of proving lower bounds against _low-depth_ algebraic formulas for
computing _low-degree_ polynomials, which naturally raises the question of
obtaining the best possible depth-reduction results in this setting.

More specifically, Limaye, Srinivasan, and Tavenas [LST21b] showed how to
prove lower bounds against algebraic formulas (and even circuits) of small
depth. Their proof proceeds by converting an algebraic formula of size $s$ and
depth $\Delta$ to a homogeneous algebraic formula of size
$\mathop{\mathrm{poly}}(s)$ and depth $O(\Delta),$ and then proving lower
bounds against homogeneous algebraic formulas of depth $O(\Delta)$. An
important point regarding the first step is that it only works in the “low-
degree setting” of $d=O(\log s/\log\log s).$ The second step proves lower
bounds against homogeneous formulas of depth up to $O(\log\log d).$

To make this proof idea work for general (unbounded-depth) algebraic formulas,
we would like to be able to homogenize and depth-reduce algebraic formulas as
much as possible. The aforementioned result of Raz [Raz13] already shows that
we can homogenize algebraic formulas efficiently in the low-degree setting. So
it is natural to investigate the best possible depth-reduction for homogeneous
algebraic formulas in the low-degree setting.

#### Results.

Our main result is a depth-reduction result for homogeneous formulas that
efficiently reduces the depth to $O(\log d)$, matching what was already known
for algebraic circuits by the result of [VSBR83].

######  Theorem 1 (Main Result).

Let $F$ be a homogeneous algebraic formula of size $s$ computing a polynomial
$P$ of degree $d\geq 2$. Then $P$ is also computed by a homogeneous formula
$F^{\prime}$ of size $\mathop{\mathrm{poly}}(s)$ and depth $O(\log d).$
Moreover, if $F$ is monotone and/or non-commutative, then so is $F^{\prime}$.

Here, a _monotone_ algebraic formula is one that does not exploit
cancellations in any way, and a _non-commutative_ formula describes a
polynomial expression in a domain where the input variables do not commute
when multiplied with each other (formal definitions are given in Section 2).
These are both settings in which formula upper bounds are harder to prove, and
hence the depth-reduction result in this setting implies the result in the
standard setting. It can also be checked that the depth-reduction procedure
above preserves other interesting properties of the formula, such as
_multilinearity_ and _set-multilinearity_.

Using the aforementioned result of Raz that allows us to homogenize algebraic
formulas in the low-degree setting, we get the following depth-reduction even
for _inhomogeneous_ formulas.

######  Corollary 2.

Let $d=O(\log n)$. Then a homogeneous polynomial $P$ defined on $n$ variables
with degree $d\geq 2$ has an algebraic formula of size
$\mathop{\mathrm{poly}}(n)$ if and only if it has an algebraic formula of
depth $O(\log d)$ and size $\mathop{\mathrm{poly}}(n).$

In particular, this means that to prove superpolynomial lower bounds against
general algebraic formulas in the low-degree setting, it suffices to prove
such lower bounds against homogeneous algebraic formulas of depth $O(\log d).$
As far as we know, nothing below the trivial $O(d)$ bound was known before for
such an implication. This brings us much closer to the regime of depths for
which we have lower bounds [LST21b].

The statements are even starker in the non-commutative setting, where it is a
long-standing problem to prove separations between _Algebraic Branching
Programs_ (ABPs) and formulas. In recent work [TLS22], it was shown how to
prove such a result for depths that are $o(\sqrt{\log d})$. The results of
this paper show that it suffices to prove such a result for depth $O(\log
d).$777We note that Raz’s result, though only stated for the commutative
setting, works just as well in the non-commutative case.

Finally, we also show that our results cannot be improved asymptotically in
terms of depth, unless we use techniques that exploit cancellations in some
way.

######  Theorem 3 (Lower Bound).

Let $n$ and $d=d(n)$ be growing parameters such that $d(n)\leq\sqrt{n}$. Then
there is a monotone algebraic formula $F$ of size at most $n$ and depth
$O(\log d)$ computing a polynomial $P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ of
degree at most $d$ such that any monotone formula $F^{\prime}$ of depth
$o(\log d)$ computing $P$ must have size $n^{\omega(1)}.$

It should be noted that a well-known result of Gupta, Kamath, Kayal and
Saptharishi [GKKS16] shows how to exploit cancellations to obtain better
depth-reduction results. However, in general this does not reduce the depth of
a given formula by more than a constant factor without incurring a significant
blow-up in size.888More precisely, the result of [GKKS16] shows how to convert
a low-degree _homogeneous_ depth-$4$ formula to an _inhomogeneous_ depth-$3$
formula efficiently. In general, this can be used to reduce the depth of a
small-depth formula by a multiplicative factor of $2$. As a result, we believe
that the above result is a strong indication that our depth reduction result
is tight up to a constant factor in the depth.

##  2 Preliminaries

#### Basic notation.

Throughout, unless otherwise specified, we work with polynomials over a field
$\mathbb{F}$. We will work with the multivariate ring of polynomials
$\mathbb{F}[x_{1},\ldots,x_{n}]$ or its _non-commutative_ analog
$\mathbb{F}\langle x_{1},\ldots,x_{n}\rangle.$

###  2.1 Algebraic formulas

We start with some brief definitions and results related to algebraic
formulas. For much more about this model, see the standard references [SY10,
Sap15].

#### The model.

An algebraic formula over the multivariate polynomial ring
$\mathbb{F}[x_{1},\ldots,x_{n}]$ is a rooted, directed tree with edges
directed towards the root. Leaves are labelled by variables
$x_{1},\ldots,x_{n}$ or by the constant $1$ and edges by non-zero field
constants. Internal nodes (i.e., gates) by $+$ and $\times$ and compute linear
combinations (based on the edge weights) or products of their children. We
will assume, with loss of generality, that if a node $\alpha$ has for child a
leaf labelled by $1$, then $\alpha$ is a $+$-gate and that if a $+$-gate
$\alpha$ has only children labelled by $1$, then $\alpha$ is the output of the
formula.999This ensures that a formula can compute polynomials with a constant
term but forbids using many arithmetic operations just to compute constants. A
_non-commutative_ algebraic formula over the multivariate polynomial ring
$\mathbb{F}\langle x_{1},\ldots,x_{n}\rangle$ is defined similarly, with the
additional assumption that the children of any $\times$-gate are linearly
ordered, and the corresponding product is computed in this order.

Unless explicitly stated, the algebraic formulas we consider have _unbounded_
fan-in (i.e., a gate can have any number of inputs). The _size_ of $F$ will
denote the number of leaves,101010This is within a constant factor of the
number of gates, as long as each gate has fan-in at least $2$ each (which is
without loss of generality). the _depth_ of $F$ the longest leaf-to-root path.
The _product-depth_ and the _sum-depth_ of $F$ are defined to be the maximum
number of product gates and sum gates encountered on a leaf-to-root path,
respectively.

A _parse tree_ of a formula $F$ is a subformula of $F$ which corresponds to
the way a monomial is built in the evaluation of $F$. Parse trees of $F$ can
be defined inductively as follows:

  * •

If $F$ has a top $+$-gate, a parse tree of $F$ is obtained by taking a parse
tree of one of its children together with the corresponding edge to the root
of $F$;

  * •

If $F$ has a top $\times$-gate, a parse tree of $F$ is obtained by a taking a
parse tree of each of its children, together with the incoming edges of the
root of $F$;

  * •

The only parse tree of a leaf is itself.

The polynomial computed by a parse tree is a single monomial, which is equal
to the product of the variables labelling its leaves, multiplied by the
product of the scalars labelling its edges. The polynomial computed by a
formula $F$ is easily seen to be the sum of the monomials computed by all its
parse trees.

A formula $F$ is called _monotone_ if any monomial computed by a parse tree of
$F$ has a non-zero coefficient in the polynomial computed by $F$.

We now recall some well-known results from the literature regarding algebraic
formulas. It should be noted that these results (specifically Theorems 4, 5
and 10 later on) are usually proved in the general setting of commutative
formulas. However, it is easy to see that the proofs of these results carry
over to the monotone, non-commutative setting without significant change.

#### Depth-reduction.

Classical results [BKM73, Bre74] show that any algebraic formula of small size
can be simulated by one of small depth and not much larger size. Formally,

######  Theorem 4.

Let $F$ be a (non-commutative or commutative) algebraic formula of size $s$
computing a polynomial $P$. Then there is an algebraic formula $F^{\prime}$ of
size at most $\mathop{\mathrm{poly}}(s)$ and depth $\Delta=O(\log s)$
computing $P$. We may also assume that each gate in $F^{\prime}$ has fan-in
$2$. Furthermore, $F$ is homogeneous and/or monotone, then so is $F^{\prime}$.

#### Homogeneity.

Each gate in an algebraic formula has a _syntactic degree_ defined in a
natural way. Leaves labelled by the constant $1$ have syntactic degree $0$,
leaves labelled with a variable have syntactic degree $1$, $\times$-gates have
a syntactic degree that is the sum of the syntactic degrees of their children,
and $+$-gates have a syntactic degree that is equal to the largest of the
syntactic degrees of their children. The syntactic degree of a formula is
defined as the syntactic degree of its output. Notice that in a formula the
syntactic degree of any gate is bounded by the syntactic degree of the
formula.

We will further assume that no gate computes the zero polynomial.

A formula is _homogeneous_ if each gate in the formula computes a homogeneous
polynomial. Equivalently, in terms of syntactic degrees, this means that all
the children of a sum gate have the same syntactic degree.

Raz [Raz13] showed how to convert a possibly inhomogeneous formula $F$ to a
homogeneous formula with a relatively small blow-up in size.

######  Theorem 5.

Let $F$ be a (non-commutative or commutative) algebraic formula of size $s$
and product-depth $\Delta$ computing a polynomial $P$ such that all gates in
$F$ have fan-in $2$. Then there is a _homogeneous_ algebraic formula
$F^{\prime}$ of size at most $O\left(s\cdot\binom{\Delta+d+1}{d}\right)$ and
product-depth $\Delta$ computing $P$. In particular, if $\Delta=O(\log s)$ and
$d=O(\log s)$, then the formula $F^{\prime}$ has size
$\mathop{\mathrm{poly}}(s).$

##  3 Main result

#### Proof Overview.

While the proof of the main result is fairly short and (in our opinion) clean,
we add some remarks here to clarify why previous depth-reduction proofs are
not applicable in our setting.

The first attempt in proving Theorem 1 would be to try to use the proof
strategy behind Theorem 4. Here, we start with a formula $F$ of size $s$ and
find a subformula $G$ of size roughly $s/2$ rooted at some gate $\alpha$ of
$F$. It is not hard to show that the polynomial computed by $F$ can be written
as

$F=G\times H_{1}+H_{2}$

where $H_{1}$ and $H_{2}$ are also computed by formulas of size
$s/2$.111111Here, for simplicity, we are assuming that $F$ is a commutative
formula. In the non-commutative setting, we would instead get
$F=H_{1}^{\prime}GH_{1}^{\prime\prime}+H_{2}.$ We then apply induction to
these three subformulas to get the result. Unfortunately, this strategy does
not use the degree of the formula at all, and therefore only yields a formula
of depth $O(\log s).$

In the homogeneous setting, it is sometimes more natural to do induction on
the degree of the underlying formula, in which case $G$ and $H_{1}$ (in the
decomposition above) would be subformulas of degree roughly $d/2$. We get the
following recursion on the worst-case size of the depth-reduced version of
$F$, which we denote by $T(s,d)$

$T(s,d)\leq T(s_{1},d/2)+T(s-s_{1},d/2)+T(s-s_{1},d)$

where $s_{1}$ denotes the size of $G$. Unfortunately, in this case, the
formulas $H_{1}$ and $H_{2}$ _could_ have size nearly $s$, resulting in
considerable size blow-up. Indeed, when $s_{1}$ is much smaller than $s$ (say
$s_{1}=s^{o(1)}$), the above recursion only yields $T(s,d)=s^{O(\log d)}$,
which is a superpolynomial size blow-up.

It may be possible to interleave recursions with respect to size and depth,
but we were unable to make this work.

Another possible strategy could be to follow the work of [VSBR83] which
produces _circuits_ of the required depth. Unfortunately, the proof of
[VSBR83] is a memoization procedure, which seems to yield circuits even when
applied to a formula $F$. Turning the resulting circuit of depth $O(\log d)$
into a formula seems to increase the size to $s^{\Omega(\log d)}$.

The approach we take is somewhat more global than the recursive strategies
outlined above. Our first motivating example is seemingly the worst-case
example for depth-reduction: a _comb_ of depth greater than $d$ with
alternating sums and products. More formally, a comb computes the following
polynomial (up to identifying variables).

$C(x)=x_{1}+(x_{2}\times(x_{3}+(x_{4}\times\cdots)))$

Note that the above yields a formula of depth greater than $d$ where $d$ is
the degree of the underlying polynomial. However, we observe that such a comb
actually computes a polynomial with only a few monomials, and hence can be
written trivially as a depth-$2$ $\sum\prod$-formula without much of a size
blow-up.

Building on this observation, the overall strategy is to decompose the formula
into a top part $G$, which is a (generalized) comb, whose leaves are
subformulas of $F$ to which we will apply the same procedure recursively. We
then write $G$ as a $\sum\prod$-formula, and replace its leaves with the
depth-reduced versions of the subformulas. This gives the depth-reduced
version of $F$.

The correct definition of $G$ is crucial, and somewhat subtle (at least to
us), but with the proper definitions in place, the proof goes through without
much trouble.

###  3.1 Proof of Theorem 1

In this section we prove our main result (Theorem 1). We start by showing a
simple depth-reduction result for the case of _skew formulas_. A formula is
said to be skew if every multiplication gate in it has at most $1$ non-trivial
child (i.e., a non-leaf node).

We will say that a leaf in a skew-formula is a $+$-leaf if the parent of that
leaf is a $+$ gate and a $\times$-leaf otherwise. We show that any skew
formula can be converted efficiently into a depth-$2$ formula, i.e., a
$\sum\prod$-formula.

######  Lemma 6.

Let $G$ be a skew formula with sum-depth $\delta$, wherein all the gates have
fan-in $2$ and the leaves are labelled by distinct variables. Then the
polynomial computed by $G$ is a multilinear polynomial with at most
$2^{\delta}$ monomials. Moreover any variable labelling in $G$

  * •

a $+$-leaf,

  * •

or a $\times$-leaf whose sibling is a leaf

appears in exactly one monomial. We will call them the non-duplicable
variables.

###### Proof.

We prove this by induction on the depth of the formula. The base case is when
the depth is $0$ or $1$. In both cases, the statement trivially holds.

For the induction case, assume that the depth is at least $2$. Suppose
$G=G_{1}+G_{2}$. The sum-depths of $G_{1}$ and $G_{2}$ are at most $\delta-1$.
Let $f_{1},f_{2}$ be the multilinear polynomials computed by $G_{1},G_{2}$,
respectively. We know that the leaves of $G$ are labelled with distinct
variables. Hence, $G_{1},G_{2}$ have the same property and the variable sets
labelling the leaves of $G_{1}$ and $G_{2}$ are disjoint. The depths of
$G_{1}$ and $G_{2}$ are strictly smaller than the depth of $G$. By the
induction hypothesis we have that $f_{1}$ and $f_{2}$ have at most
$2^{\delta-1}$ monomials. Moreover, any non-duplicable variable in $G_{1}$
appears in at most one monomial in $f_{1}$. Similarly, any non-duplicable
variable in $G_{2}$ appears in at most one monomial in $f_{2}$. Hence, the
polynomial computed by $G$, i.e., $f_{1}+f_{2}$, has at most $2^{\delta}$
monomials and each non-duplicable variable appears in at most one monomial in
it.

Suppose the top gate of $G$ is a $\times$ gate. As $G$ is a skew formula it is
either $x\times G_{1}$ or $G_{1}\times x$, where $x$ is a variable. In
particular since the depth of $G$ is at least two, the variable $x$ is
duplicable. Let $f_{1}$ be the multilinear polynomial computed by $G_{1}$. By
our assumption, the variable $x$ does not appear in $f_{1}$. The depth of
$G_{1}$ is strictly smaller than $G$. By the induction hypothesis we have that
$f_{1}$ has at most $2^{\delta}$ monomials and any non-duplicable variable in
$G_{1}$ appears in at most one monomial. As $x$ can distribute over the
monomials of $f_{1}$, we have that the polynomial computed by $G$ is
multilinear with at most $2^{\delta}$ monomials and any non-duplicable
variable appears in at most one monomial.

(Note that this can also be seen using parse trees, since the polynomial
computed is the sum of the monomials computed by the parse trees. The
multilinearity is obvious. Note that parse trees do not really “branch” at
multiplication gates because of the skewness and are therefore combs. To build
a parse tree starting from the root we will have two choices for each addition
gate we encounter on the path, and there are at most $\delta$, so we get at
most $2^{\delta}$ parse trees. The only parse tree containing a given non-
duplicable variable is defined by the path from the root to this leaf.) ∎

If a formula is homogeneous, it implies that for any gate $\alpha$, the degree
of the polynomial computed by $\alpha$ coincides with the syntactic degree
$d_{\alpha}$ of $\alpha$. Based on this remark, below we prove a stronger
statement than Theorem 1. Specifically, Theorem 1 is stated for homogeneous
formulas. But here, we show a depth-reduction for formulas for which the
syntactic degree is small.

######  Theorem 7 (Refinement of Theorem 1).

Let $F$ be an algebraic formula of size $s$ and of syntactic degree $d_{F}\geq
2$. Then $P$ is also computed by a formula $F^{\prime}$ of size
$\mathop{\mathrm{poly}}(s)$ and depth $O(\log d_{F})$. Moreover, if $F$ is
homogeneous, monotone and/or non-commutative, then so is $F^{\prime}$.

###### Proof.

Let us start with a formula obtained from $F$ after applying Theorem 4. That
is, we will assume that we have a formula of size $\mathop{\mathrm{poly}}(s)$
such each gate in it has fan-in $2$, sum-depth and product-depth are bounded
by $O(\log s)$. For notational simplicity, from now on, $F$ will refer to this
new formula.

Let $\delta$ be a positive integer. For a formula $G$ of syntactic degree
$d_{G}\geq 1$ and sum-depth $\Delta(G)$ we define a potential function
$\phi_{\delta}(G)$ as follows.

$\left\\{\begin{aligned} \phi_{\delta,1}(G)&=\lceil\log(d_{G})\rceil\\\
\phi_{\delta,2}(G)&=\lceil\Delta(G)/\delta\rceil\end{aligned}\right.$

and let

$\phi_{\delta}(G)=\phi_{\delta,1}(G)+\phi_{\delta,2}(G).$

We will show that the potential function bounds the depth of the depth-reduced
formula that we will construct. We will also use it to bound the size of the
resulting formula. Specifically, we prove the following lemma.

######  Lemma 8.

Let $\delta$ be a positive integer. Any formula $F$ of fan-in $2$, syntactic
degree $d\geq 1$, sum-depth $\Delta$, and size $s$ can be parallelized into a
formula $F^{\prime}$ (of arbitrary fan-in) of product-depth at most
$\phi_{\delta}(F)$ and size at most $s\cdot 2^{\delta\log(d)}$. Further, if
$F$ is homogeneous, monotone and/or non-commutative, so is $F^{\prime}$.

Since we ensured that the sum-depth is bounded by $O(\log s)$, taking
$\delta=\left\lceil\frac{\log s}{\log d}\right\rceil$ and applying Lemma 8, we
get that the final formula $F^{\prime}$ has size at most
$\mathop{\mathrm{poly}}(s)$ and product-depth at most

$\phi_{\delta}(F)=O\left(\lceil\log d\rceil+\left\lceil\log(s)\frac{\log
d}{\log s}\right\rceil\right)=O(\log d).$

By collapsing sum gates that feed into other sum gates, we see that the depth
of $F^{\prime}$ can be assumed to be at most twice its product-depth, which is
$O(\log d)$. This thus finishes the proof of the theorem. ∎

We now prove Lemma 8.

###### Proof of Lemma 8.

For any gate $\alpha$ in $F$, let $F_{\alpha}$ denote the subformula rooted at
$\alpha$ and $d_{\alpha}$ be its syntactic degree. We do the proof by
induction on $\phi_{\delta}(F)$.

The base case $\phi_{\delta}(F)=0$ trivially holds. Consider the following set
of gates of $F$:

$\mathcal{A}=\left\\{\alpha\mid\alpha\text{ is a not a leaf labelled~{}$1$ and
}\phi_{\delta}(F_{\alpha})<\phi_{\delta}(F)=\phi_{\delta}(F_{\text{parent}(\alpha)})\right\\}.$

For any gate $\alpha$ in $\mathcal{A}$, the induction hypothesis tells us that
we can construct a formula $F_{\alpha}^{\prime}$ of product-depth at most
$\phi_{\delta}(F)-1$ and size at most $s_{\alpha}\cdot
2^{\delta\log(d_{\alpha})}$ computing the same polynomial as $F_{\alpha}.$

Let us consider the formula $G$ obtained by replacing these gates from
$\mathcal{A}$ in $F$ by leaves (labelled with distinct variables). Notice that
for a product-gate $\beta$ in $F$, at most one of its children has syntactic
degree larger than $d_{\beta}/2$, where $d_{\beta}$ is the syntactic degree of
$\beta$. Consequently, $G$ is a skew formula. The other child of $\beta$ is a
$\times$-leaf in $G$. Moreover, $G$ has sum-depth at most $\delta$ (since
$\phi_{\delta,2}$ strictly decreases for gates below).

Hence, we can use Lemma 6 to simplify $G$: we get that the polynomial computed
by $G$ is a multilinear polynomial in its leaves and has $2^{\delta}$
monomials. We can then write $G$ as a $\sum\prod$-formula $G^{\prime}$ such
that each duplicable gate appears in at most $2^{\delta}$ monomials and each
non-duplicable gate in at most $1$.

The new formula $F^{\prime}$ for $F$ is obtained from $G^{\prime}$ by
replacing each variable leaf, which corresponds to some gate $\alpha$ in $F$,
by its depth-reduced version $F^{\prime}_{\alpha}$ constructed using the
induction hypothesis above.

The product-depth of $F^{\prime}$ is bounded by the product-depth of the gates
$\alpha\in\mathcal{A}$ plus the product-depth of $G$, which is equal to $1$
after rewriting it as a $\sum\prod$-formula. That is, the product-depth is at
most $(\phi_{\delta}(F)-1)+1=\phi_{\delta}(F)$. By construction if $G$ does
not contain leaves labelled by $1$, then it is also the case for $G^{\prime}$,
otherwise, $G^{\prime}$ still has at most one such leaf. The size of the
resulting formula is bounded by

$\sum_{\alpha\ \text{non-duplicable }}\left(s_{\alpha}\cdot
2^{\delta\log(d_{\alpha})}\right)+\left(2^{\delta}\cdot\sum_{\alpha\
\text{duplicable}}\left(s_{\alpha}\cdot
2^{\delta\log(d_{\alpha})}\right)\right)+\mathbbm{1}_{\text{G' has a constant
leaf}}.$

Notice that if $\alpha$ is duplicable, it must be a $\times$-leaf with its
sibling $\beta$ not a leaf. This means that $d_{\alpha}\leq d_{\beta}\leq d$
since the syntactic degree is maximal at the root. Hence $d_{\alpha}\leq d/2$
so the contribution of duplicable gates is bounded by

$\sum_{\alpha\ \text{duplicable }}2^{\delta}\left(s_{\alpha}\cdot
2^{\delta\left(\log(d)-1\right)}\right)\leq\sum_{\alpha\ \text{duplicable
}}\left(s_{\alpha}\cdot 2^{\delta\log(d)}\right).$

The contribution of non-duplicable gates is bounded by

$\sum_{\alpha\ \text{non-duplicable }}s_{\alpha}\cdot 2^{\delta\log d}$

since any gate in $F$ has syntactic degree at most $d$. By the choice of
$\mathcal{A}$, the subformulas $F_{\alpha}$ are disjoint so
$\sum_{\alpha\in\mathcal{A}}s_{\alpha}\leq s$, with strict inequality if
$G^{\prime}$ has a constant leaf. Hence the size of $F^{\prime}$ is bounded by
$s\cdot 2^{\delta\log(d)}$.

Finally, it is straightforward to verify that the construction preserves
homogeneity, monotonicity and/or non-commutativity. ∎

######  Remark 9.

It is easy to note that our depth reduction procedure does not increase the
syntactic degree of the formula.

We also observe that putting Theorem 1 together with Theorems 4 and 5
immediately implies Corollary 2.

###### Proof of Corollary 2.

Given a (possibly inhomogeneous) formula $F$ of size
$s=\mathop{\mathrm{poly}}(n)$ computing a polynomial of degree $d=O(\log n),$
we first apply standard depth-reduction (Theorem 4) to get an equivalent
formula $F_{1}$ of size $s_{1}=\mathop{\mathrm{poly}}(n)$ and depth
$\Delta_{1}=O(\log n)$ where each gate has fan-in $2$. Applying Raz’s
homogenization theorem (Theorem 5) to $F_{1}$ yields an equivalent
_homogeneous_ formula $F_{2}$ of size $s_{2}=\mathop{\mathrm{poly}}(n)$ and
depth $\Delta_{2}=O(\log n)$. We can now apply Theorem 1 to $F_{2}$ to get an
equivalent formula $F^{\prime}$ of size $s^{\prime}=\mathop{\mathrm{poly}}(n)$
and depth $\Delta^{\prime}=O(\log d).$ ∎

###  3.2 Reducing the size blow-up

We note that the above strategy can be easily adapted to yield a small depth
formula of size $s^{\prime}$ that is nearly linear in the size $s$ of the
original formula, at the expense of increasing the depth by a large constant.

The proof is nearly identical to the proof of Theorem 1 above. The new
ingredient is a near-linear depth-reduction in the setting where there is no
bound assumed on the degree of the above formula. More precisely, Bshouty,
Cleve and Eberly [BCE95] (see also the work of Bonet and Buss [BB94]) showed
the following (we sketch Bonet and Buss’ proof in Appendix A for
completeness).

######  Theorem 10 (Depth-reduction with near-linear size).

The following holds for any $\varepsilon>0.$ Let $F$ be a (non-commutative or
commutative) algebraic formula of size $s$ computing a polynomial $P$. Then
there is an algebraic formula $F^{\prime}$ of size at most $s^{1+\varepsilon}$
and depth $\Delta=2^{O(1/\varepsilon)}\cdot\log s$ computing $P$. We may also
assume that each gate in $F^{\prime}$ has fan-in $2$. Furthermore, if $F$ is
homogeneous and/or monotone, then so is $F^{\prime}$.

Using the above result, we can prove the following improved version of our
depth-reduction.

######  Theorem 11.

Assume that $F$ is a (commutative or non-commutative) formula of size $s$ and
syntactic degree $d\geq 1$ computing a polynomial $P$. Then $P$ is also
computed by a formula $F^{\prime\prime}$ of size at most $s^{1+\varepsilon}$
and depth $\Delta=2^{O(1/\varepsilon)}\cdot\log d.$ Furthermore, if $F$ is a
homogeneous and/or monotone formula, then so is $F^{\prime\prime}$.

###### Proof.

If $d^{4/\varepsilon}\geq s$, then the depth-reduction of Theorem 10 already
gives a satisfactory solution. Indeed the size is bounded by
$s^{1+\varepsilon}$ and the depth is bounded by

$2^{O(1/\varepsilon)}\log s\leq\frac{4}{\varepsilon}2^{O(1/\varepsilon)}\log
d\leq 2^{O(1/\varepsilon)}\log d.$

So we assume that $s>d^{4/\varepsilon}$. By first applying Theorem 10 (with
$\varepsilon/2$ instead of $\varepsilon$), we obtain a formula $F^{\prime}$ of
size at most $s^{1+\varepsilon/2}$, depth
$\Delta^{\prime}=2^{O(1/\varepsilon)}\cdot\log s$, and fan-in $2$ computing
$P$.

Now, we apply Lemma 8, while setting $\delta=\lfloor{(\varepsilon\log
s)}/{(2\log d)}\rfloor$. Notice that since $\varepsilon\log s>4\log d$, it
ensures that $\delta>(\varepsilon\log s)/(4\log d)>1$.

Then the strategy produces a formula $F^{\prime\prime}$ of product-depth at
most

$\phi_{\delta}(F^{\prime})\leq\phi_{\delta,1}(F^{\prime})+\phi_{\delta,2}(F^{\prime})<\lceil\log
d\rceil+2^{O(1/\varepsilon)}\log s\frac{4\log d}{\varepsilon\log
s}=2^{O(1/\varepsilon)}\log d$

and size at most

$s^{1+\varepsilon/2}\cdot 2^{\delta\log d}\leq
s^{1+\varepsilon/2}s^{\varepsilon/2}.$

This proves the theorem. ∎

###  3.3 Reducing the product fan-ins to 2

It is natural to ask if Theorem 1 can be proved while ensuring that the fan-in
of each gate is bounded by $2$, as in Theorem 1 and Theorem 10. This is not
possible, as a formula of fan-in $2$ and depth $O(\log d)$ can only compute
polynomials on at most $\mathop{\mathrm{poly}}(d)$ variables, while formulas
of size $s$ may have up to $s$ variables. However, this does not rule out
reducing the fan-in of the product gates to $2$. Indeed, the _circuit_ depth-
reduction of [VSBR83] does exactly this. We show now that this can also be
done for algebraic formulas with bounded syntactic degree.

######  Theorem 12.

Let $F$ be a (commutative or non-commutative) algebraic formula $F$ of size
$s$, depth $\Delta$, and syntactic degree $d\geq 1$ computing a polynomial
$P$. Then $P$ can also be computed by a formula $F^{\prime}$ of size $s$ and
depth $\Delta^{\prime}=O(\Delta+\log d)$ where each product gate of
$F^{\prime}$ has fan-in $2$. Furthermore, if $F$ is a homogeneous and/or
monotone formula, then so is $F^{\prime}$.

Plugging this in Theorem 7 gives a depth-reduction to formulas of depth
$O(\log d)$ and size $\mathop{\mathrm{poly}}(s)$ such that all product gates
have fan-in at most $2$. A similar result can be obtained with a smaller blow-
up in size by combining this statement with Theorem 11.

###### Proof.

It suffices to prove a weaker version of the above theorem where each product
gate has fan-in at most $3$. We can then replace each of the products of fan-
in $3$ by a tree of product gates of fan-in $2$ and size $3$. This has the
effect of increasing the depth at most by a factor of $2$, which does not
affect the overall result.

So we will prove this slightly weaker version. In this setting, we will aim
for a depth $\Delta^{\prime}=\Delta+\log d.$

This is done by induction on the depth $\Delta$ of the formula. The case of
$\Delta=0$ is trivial. Let $F$ be a formula of depth $\Delta>0$ and syntactic
degree $d$.

Assume that the output gate of $F$ is a sum gate, and $F_{1},\ldots,F_{t}$ are
the subformulas of $F$ of depth $\Delta-1$. By definition, each $F_{i}$ has
syntactic degree at most $d$. Applying the induction hypothesis to each of the
$F_{i}$ yields a formula $F_{i}^{\prime}$ with product gates of fan-in at most
$3$. The formula $F^{\prime}$ can then be defined as the sum of these
formulas.

Now we come to the main case, which is when the output gate of $F$ is a
product gate. Assume that $F_{1},\ldots,F_{t}$ are the subformulas of $F$ of
depth $\Delta-1$ in the order121212The order is important in the non-
commutative setting. that they appear in $F$. Let $d_{i}$ denote the syntactic
degree of $F_{i}$. Define

$m=\min\\{j\ |\sum_{i=1}^{j}d_{i}\geq d/2\\}.$

Let $F_{\ell}$ be the formula obtained from $F$ by keeping only the
subformulas $F_{1},\ldots,F_{m-1}$, and $F_{r}$ be the formula obtained by
keeping only $F_{m+1},\ldots,F_{t}.$ We use the induction hypothesis on
$F_{\ell},F_{m},$ and $F_{r}$ to get formulas
$F_{\ell}^{\prime},F_{m}^{\prime}$ and $F_{r}^{\prime}$. Finally, we set

$F^{\prime}=F_{\ell}^{\prime}\times F_{m}^{\prime}\times F_{r}^{\prime}.$

The size131313Recall that the size of a formula is the number of its leaves.
of $F^{\prime}$ is the sum of the sizes of $F_{\ell}^{\prime},F_{m}^{\prime}$
and $F_{r}^{\prime}$, which is at most $s$ by the induction hypothesis. Let
$\Delta_{\ell}^{\prime},\Delta_{m}^{\prime}$ and $\Delta_{r}^{\prime}$ denote
the depths of $F_{\ell}^{\prime},F_{m}^{\prime}$ and $F_{r}^{\prime}$
respectively. The depth of $F^{\prime}$ is

$1+\max\\{\Delta_{\ell}^{\prime},\Delta_{m}^{\prime},\Delta_{r}^{\prime}\\}\leq
1+\max\\{\Delta+\log(d/2),\Delta-1+\log d,\Delta+\log(d/2)\\}=\Delta+\log d$

where the second inequality uses the induction hypothesis, and the fact that
$F_{\ell}$ and $F_{r}$ have syntactic degree at most $d/2$ and $F_{m}$ has
depth at most $\Delta-1.$ ∎

##  4 Tightness

Given integers $k\geq 1$ and $r\geq 2$, we will define a polynomial
$H^{(k,r)}$. Intuitively, we want to define this polynomial as a standard
universal polynomial for formulas. It is composed of $k$-nested inner
products, each one of size $r$. In the following we will drop the superscript
in $H^{(k,r)}$ and write simply $H$ instead.

The polynomial $H$ will be defined over the set of $(2r)^{k}$ variables

$\\{x_{\sigma,\tau}\ |\ \sigma\in[2]^{k},\tau\in[r]^{k}\\}.$

Let us define recursively polynomials $H_{u,v}$ for all $(u,v)\in[2]^{\leq
k}\times[r]^{\leq k}$ such that $|u|=|v|$:

$\displaystyle H_{u,v}=$ $\displaystyle\ x_{u,v}$ $\displaystyle\text{when
}|u|=|v|=k$ $\displaystyle H_{u,v}=$
$\displaystyle\sum_{a=1}^{r}H_{u1,va}H_{u2,va}$
$\displaystyle\text{otherwise}.$

The polynomial $H$ is defined as the polynomial $H_{\varepsilon,\varepsilon}$.
Note that $H$ is a polynomial of degree $d=2^{k}$ and has $r^{d-1}$ monomials.

From its definition, $H$ is computed by a monotone formula $M$ of size
$(2r)^{k}$ and depth $2k$, with a $+$-gate at the top, alternating layers of
$+$-gates and $\times$-gates, with $+$-gates of fan-in $r$ and $\times$-gates
of fan-in $2$, and leaves labelled with distinct variables.

For words $u$ and $v$ over the same alphabet, we write $u\sqsupset v$ if $u$
is a prefix of $v$. There is a natural one-to-one correspondance between
prefixes of words of $([r]\times[2])^{k}$ and nodes of $M$, which is the
following. Let $\sigma=\sigma_{1}\ldots\sigma_{k}\in[2]^{k}$, and
$\tau=\tau_{1}\ldots\tau_{k}\in[r]^{k}$. The word
$\tau_{1}\sigma_{1}\ldots\tau_{k}\sigma_{k}$ corresponds to a path from the
root of $M$ to the leaf labelled $x_{\sigma,\tau}$, while proper prefixes of
$\tau_{1}\sigma_{1}\ldots\tau_{k}\sigma_{k}$ correspond to internal gates in
$M$ along this path. For $\ell<k$, $u=u_{1}\ldots u_{\ell}\in[2]^{\ell}$ and
$v=v_{1}\ldots v_{\ell}\in[r]^{\ell}$, the node which corresponds to the word
$v_{1}u_{1}\ldots v_{\ell}u_{\ell}$ is the $+$-gate of $M$ computing
$H_{u,v}$.

The polynomial $H$ is easily seen to be set-multilinear with respect to the
sets of variables $\\{X_{\sigma}\ |\ \sigma\in[2]^{k}\\}$ where
$X_{\sigma}=\\{x_{\sigma,\tau}\ |\ \tau\in[r]^{k}\\}$. This means that each
monomial has exactly one variable from each set $X_{\sigma}$.

######  Remark 13.

For $|u|=|v|=\ell\leq k$, $u\in[2]^{\ell}$ and $v\in[r]^{\ell}$, the
polynomial $H^{(k,r)}_{u,v}$ is defined over the set of variables

$X_{u,v}=\\{x_{\sigma,\tau}\ |\ \sigma\in[2]^{k},\
\tau\in[r]^{k},u\sqsupset\sigma,\ v\sqsupset\tau\\}$

and is the polynomial $H^{(k-\ell,r)}$ (upto renaming of the variables). In
particular, its degree is $d^{\prime}=2^{k-\ell}$, it has $r^{d^{\prime}-1}$
monomials and it is set-multilinear with respect to $\\{X_{\sigma}\ |\
\sigma\in[2]^{k},\ u\sqsupset\sigma\\}$.

Before proving hardness of $H$ for small-depth monotone formulas, we need to
show that the gates of a monotone formula computing $H$ cannot compute too
many monomials. This is proved in Lemma 15 below.

######  Proposition 14.

Consider two variables $x_{\sigma,\tau}$ and
$x_{\sigma^{\prime},\tau^{\prime}}$. If
$x_{\sigma,\tau}x_{\sigma^{\prime},\tau^{\prime}}$ appears in a monomial of
$H$, and if $\sigma$ and $\sigma^{\prime}$ have a common prefix of length
$\ell<k$, then $\tau$ and $\tau^{\prime}$ have a common prefix of length
$\ell+1$.

###### Proof.

Observe that $x_{\sigma_{1},\tau_{1}}\ldots x_{\sigma_{p},\tau_{p}}$ is a
monomial of $H$ if and only if these variables form the leaves of a parse tree
of $M$. As observed above, the root-to-leaf path leading to the variable
$x_{\sigma_{i},\tau_{i}}$ in $M$ is obtained by taking in turn the first
letter of $\tau_{i}$, the first letter of $\sigma_{i}$, the second letter of
$\tau_{i}$, etc.

If the product $x_{\sigma,\tau}x_{\sigma^{\prime},\tau^{\prime}}$ appears in a
monomial of $H$, it must be possible to complete the union of the two paths,
from the root to $x_{\sigma,\tau}$ and from the root to
$x_{\sigma^{\prime},\tau^{\prime}}$, into a parse tree of the formula $M$.

If the longest common prefix of $\tau$ and $\tau^{\prime}$ were of length at
most $\ell$, then the lowest common ancestor of $x_{\sigma,\tau}$ and
$x_{\sigma^{\prime},\tau^{\prime}}$ in $M$ would be a $+$-gate, which is not
possible in a parse tree where each $+$-gate has a single child. ∎

######  Lemma 15.

If $F$ is a monotone formula which computes the polynomial $H$ and if $\alpha$
is a gate of $F$ of degree $d_{\alpha}$, then the number of monomials of the
polynomial computed at gate $\alpha$ is at most $r^{d_{\alpha}-1}$.

###### Proof.

Since $H$ has $r^{d-1}$ monomials, the result is true when $d_{\alpha}=d$ by
monotonicity. Assume now that $d_{\alpha}<d$.

Let

$I=\\{\sigma\in[2]^{k}\ |\ \text{some variable of $X_{\sigma}$ appears in
$\alpha$}\\}.$

For $u\in[2]^{\leqslant k}$, let $I_{u}=\\{\sigma\in[2]^{k}\ |\
u\sqsupset\sigma\\}$. Let $\\{u_{1},\ldots,u_{p}\\}$ be the set of words $w$
of minimal length such that $I_{w}\subseteq I$. Then $I$ is the disjoint union
$\bigcup_{\ell\in[p]}I_{u_{\ell}}$. Since $d_{\alpha}<d$, $I\neq[2]^{k}$ so no
$u_{\ell}$ is the empty word.

Consider some $\ell\in[p]$. Let $\bar{u}_{\ell}$ be obtained by switching the
last letter of $u_{\ell}$. By minimality of the length of $u_{\ell}$, we must
have $I_{\bar{u}_{\ell}}\nsubseteq I$. Let $\sigma$ be a word in
$I_{\bar{u}_{\ell}}\setminus I$. Since $F$ is monotone and computes a set-
multilinear polynomial, it is a set-multilinear formula and therefore the
polynomial computed at $\alpha$ must be multiplied by some variable
$x_{\sigma,\tau}$. Let $v_{\ell}$ be the prefix of length $|u_{\ell}|$ of
$\tau$. Consider any variable $x_{\sigma^{\prime},\tau^{\prime}}$ appearing in
$\alpha$ such that $u_{\ell}\sqsupset\sigma^{\prime}$. Since the product
$x_{\sigma,\tau}x_{\sigma^{\prime},\tau^{\prime}}$ must appear in a monomial
of $H$ by monotonicity, it must be that $v_{\ell}\sqsupset\tau^{\prime}$ by
Proposition 14.

Any monomial $m$ in the polynomial computed in gate $\alpha$ can be written in
a unique way $m=m_{1}\cdots m_{p}$ with $m_{\ell}$ set-multilinear with
respect to $\\{X_{\sigma}\ |\ u_{\ell}\sqsupset\sigma\\}$. By the above,
$m_{\ell}$ is a monomial over the variables $X_{u_{\ell},v_{\ell}}$ of degree
$|I_{u_{\ell}}|$. By monotonicity, it should be possible to complete leaves of
$M$ labelled with variables from $m_{\ell}$ into a parse tree of $M$ appearing
in $H$, which proves that $m_{\ell}$ is a monomial of $H_{u_{\ell},v_{\ell}}$.
There are at most $r^{|I_{u_{\ell}}|-1}$ such submonomials $m_{\ell}$ by
Remark 13. It follows that the number of monomials of the polynomial computed
in node $\alpha$ is at most

$\prod_{\ell=1}^{p}r^{\lvert I_{u_{\ell}}\rvert-1}\leq r^{\lvert
I\rvert-1}=r^{d_{\alpha}-1}.\qed$

We are ready to prove hardness of the polynomial $H$ for monotone computation.
We shall make use of the following “product lemma”, which comes in different
forms in e.g. [SY10, HY11, Sap15].

######  Lemma 16.

A degree-$d$ homogeneous formula $F$ of size $s$ and product-depth $\Delta$
can be written as a sum of $O(s)$ polynomials, each of which is a product of
$\Omega(\Delta d^{1/\Delta})$ many polynomials of positive degree. Moreover,
each of these polynomials is computed by some gate in $F$.

######  Proposition 17.

If $F$ is a monotone formula of product-depth $\Delta\leq\log d$ which
computes $H$, then its size is at least $r^{\Omega(\Delta d^{1/\Delta})}$.

###### Proof.

Let $t=\Delta d^{1/\Delta}$. Since $F$ is monotone, it is homogeneous and by
Lemma 16 can be written as

$F=\sum_{i=1}^{s^{\prime}}\prod_{j=1}^{t_{i}}F_{i,j}$

with $s^{\prime}=O(s)$ and $t_{i}=\Omega(t)$ for all $i$, and $F_{i,j}$ is of
degree at least $1$ and computed by some gate in $F$.

Let $d_{i,j}$ be the degree of $F_{i,j}$. By Lemma 15, each $F_{i,j}$ computes
at most $r^{d_{i,j}-1}$ monomials. The number of monomials of
$\prod_{i=1}^{t_{j}}F_{i,j}$ is therefore bounded by

$\prod_{j=1}^{t_{i}}r^{d_{i,j}-1}\leq r^{\sum_{j=1}^{t_{i}}d_{i,j}-t_{i}}\leq
r^{d-t}$

since $\sum_{j=1}^{t_{i}}d_{i,j}=d$. It follows that the number of monomials
computed by $F$ is at most $s\cdot r^{d-t}$. Since $F$ computes $H$ which has
$r^{d-1}$ monomials, we get $s=r^{\Omega(t)}$. ∎

We can now get Theorem 3 from the introduction, which is restated here for
convenience.

######  Theorem 18.

Let $n$ and $d=d(n)$ be growing parameters such that $d(n)\leq\sqrt{n}$. Then
there is a monotone algebraic formula $F$ of size at most $n$ and depth
$O(\log d)$ computing a polynomial $P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ of
degree at most $d$ such that any monotone formula $F^{\prime}$ of depth
$o(\log d)$ computing $P$ must have size $n^{\omega(1)}.$

###### Proof of Theorem 3.

Choose parameters $k(n)$ and $r(n)$ such that $P(n):=H^{(k,r)}$ has
$\Theta(n)$ variables and degree $\Theta(d)$: let $k=\log d$ and
$r=\frac{1}{2}n^{1/\log d}$. Condition $d(n)\leq\sqrt{n}$ ensures that
$r\geqslant 2$. The polynomial $P$ has a monotone formula of size $O(n)$ and
depth $O(\log d)$. By Proposition 17, any monotone formula of product-depth
$\Delta\leq\log d$ computing $P$ has size

$r^{\Omega(\Delta d^{1/\Delta})}=\left(\frac{1}{2}n^{1/\log
d}\right)^{\Omega(\Delta d^{1/\Delta})}=(n/d)^{\left(\frac{\Delta
d^{1/\Delta}}{\log d}\right)}$

which is $n^{\Omega\left(\frac{\Delta d^{1/\Delta}}{\log d}\right)}$ using the
hypothesis $d(n)\leq\sqrt{n}$. Since $\frac{\Delta d^{1/\Delta}}{\log
d}\rightarrow+\infty$ when $\Delta=o\left(\log d\right)$ this bound is
$n^{\omega(1)}.$ ∎

##  5 Conclusion and Open questions

In this paper we investigated the possibility of reducing the depth of a
formula of size $s$ computing a polynomial of degree $d$ to $O(\log d)$ while
keeping the size $s^{O(1)}$.

We showed (Theorem 1) that we can do such a transformation when $F$ is
homogeneous. More generally, Theorem 7 states that we can achieve it as soon
as the syntactic degree of $F$ is polynomially bounded in $d$.

#### Structure inside VF.

Let us consider a sequence of polynomials $(f_{n})$ whose number of variables
and degree are bounded polynomially in $n$ (such a family is usually called a
$p$-family, see for example [B0̈0]). We can then consider three classes of
such families:

  * •

$\text{homF}[s(n)]=\\{(f_{n})\mid f_{n}\text{ is computed by a homogeneous
formula of size }\mathop{\mathrm{poly}}(s(n))\\}$,

  * •

$\text{lowSynDegF}[s(n)]=\\{(f_{n})\mid f_{n}\text{ is computed by a formula
of size }\mathop{\mathrm{poly}}(s(n))\text{ and of}\\\ \text{ syntactic degree
}\mathop{\mathrm{poly}}(\deg(f_{n}))\\}$

  * •

$\text{lowDepthF}[s(n)]=\\{(f_{n})\mid f_{n}\text{ is computed by a formula of
size }\mathop{\mathrm{poly}}(s(n))\text{ and of}\\\ \text{ depth
}O(\log\deg(f_{n}))\\}$.

Clearly, we have the inclusion
$\text{homF}[s(n)]\subseteq\text{lowSynDegF}[s(n)]$. Also, in this paper, we
have shown the inclusion
$\text{lowSynDegF}[s(n)]\subseteq\text{lowDepthF}[s(n)]$. Consequently,

$\text{homF}[\mathop{\mathrm{poly}}(n)]\subseteq\text{lowSynDegF}[\mathop{\mathrm{poly}}(n)]\subseteq\text{lowDepthF}[\mathop{\mathrm{poly}}(n)]\subseteq\text{VF},$

and we do not know if these inclusions are strict or not.

#### The complexity of the Elementary Symmetric Polynomials.

A particularly interesting special case of the questions above comes from the
example of the _Elementary Symmetric Polynomials._ Given parameters $d,n$ with
$d\leq n,$ recall that the Elementary Symmetric polynomial
$S_{n}^{d}(x_{1},\ldots,x_{n})$ is the sum of all the multilinear monomials of
degree exactly $d$. A simple and elegant construction of Ben-Or (see [SW01])
shows that for any $d$, the polynomial $S_{n}^{d}$ has an _inhomogeneous_
formula of depth-$3$ and size $O(n^{2}).$ This puts this family of polynomials
in the class $\text{lowDepthF}[\mathop{\mathrm{poly}}(n)].$ Further, Shpilka
and Wigderson [SW01, Theorem 5.3], showed that $S_{n}^{d}$ has depth-$6$
formulas of syntactic degree at most $\mathop{\mathrm{poly}}(d),$ putting it
in the class $\text{lowSynDegF}[\mathop{\mathrm{poly}}(n)].$

However, as far as we know, there are no known
$\mathop{\mathrm{poly}}(n)$-sized homogeneous formulas for this family of
polynomials.141414A strong form of this was conjectured by Nisan and Wigderson
[NW97], which was subsequently refuted by Hrubeš and Yehudayoff [HY11].
However, this still does not yield polynomial-sized homogeneous formulas for
all elementary symmetric polynomials. In fact, under some further
restrictions, Hrubeš and Yehudayoff showed [HY11] a superpolynomial
homogeneous formula lower bound when $d=n/2$. Removing these restrictions
would show a separation between $\text{homF}[\mathop{\mathrm{poly}}(n)]$ and
$\text{lowSynDegF}[\mathop{\mathrm{poly}}(n)]$. On the other hand, if indeed
the elementary symmetric polynomials have $\mathop{\mathrm{poly}}(n)$-sized
homogeneous formulas, then this can be used to argue151515see e.g. [LST21b,
Section III] for the standard argument the same for any polynomial computed by
a depth-$3$ formula of polynomial size, hinting at a possible collapse between
$\text{homF}[\mathop{\mathrm{poly}}(n)]$ and
$\text{lowSynDegF}[\mathop{\mathrm{poly}}(n)]$.

#### Lower bounds for higher-depth formulas.

Due to the recent lower bound results of [LST21b], we know that there is an
explicit homogeneous polynomial $P(X)$ of degree $d$ on $n$ variables that
cannot be computed by any formula of size $\mathop{\mathrm{poly}}(n)$ and
depth $\varepsilon\cdot\log\log d$, for some absolute constant
$\varepsilon>0$. It turns out that the polynomial $P$ _is_ computable by an
_algebraic branching program_ and therefore, lies in the complexity class
called VBP.

It is known that VF is contained in VBP. However, we do not know whether this
containment is strict or not. Our lower bound result helps us pose a refined
version of this question. Specifically, it shows that if the lower bound from
[LST21b] can be improved from $\Omega(\log\log d)$ to $\omega(\log d)$, then
we will have separated VF from VBP.

The fact that our depth reduction carries over to the non-commutative setting,
makes a compelling case for revisiting the VF vs. VBP question in the non-
commutative setting. Specifically, a recent result of [TLS22] shows that there
is an explicit non-commutative polynomial $P(X)$ of degree $d$ on $n$
variables that cannot be computed by any non-commutative formula of size
$\mathop{\mathrm{poly}}(n)$ and depth $\varepsilon\cdot\sqrt{\log d}$. So,
improving the lower bound in this case from $\Omega(\sqrt{\log d})$ to
$\omega(\log d)$ would separate VF from VBP in the non-commutative setting.

## References

  * [AV08] Manindra Agrawal and V. Vinay.  Arithmetic circuits: A chasm at depth four.  In proceedings of Foundations of Computer Science (FOCS), pages 67–75, 2008.
  * [B0̈0] Peter Bürgisser.  Cook’s versus Valiant’s hypothesis.  Theoretical Computer Science, 235(1):71–88, 2000.
  * [BB94] Maria Luisa Bonet and Samuel R. Buss.  Size-depth tradeoffs for boolean formulae.  Information Processing Letters, 49(3):151 – 155, 1994.
  * [BCE95] Nader H. Bshouty, Richard Cleve, and Wayne Eberly.  Size-depth tradeoffs for algebraic formulas.  SIAM J. Comput., 24(4):682–705, 1995.
  * [BKM73] R. Brent, D. Kuck, and K. Maruyama.  The parallel evaluation of arithmetic expressions without division.  IEEE Transactions on Computers, C-22(5):532–534, 1973.
  * [Bre74] Richard P. Brent.  The parallel evaluation of general arithmetic expressions.  Journal of the ACM, 21(2):201–206, April 1974.
  * [CKSV16] Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, and V. Vinay.  The chasm at depth four, and tensor rank : Old results, new insights.  CoRR, abs/1606.04200, 2016.
  * [CLS18] Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan.  Small-depth multilinear formula lower bounds for iterated matrix multiplication, with applications.  In STACS, volume 96 of LIPIcs, pages 21:1–21:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018.
  * [GKKS16] Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi.  Arithmetic circuits: A chasm at depth 3.  SIAM Journal of Computing, 45(3):1064–1079, 2016.
  * [HY11] Pavel Hrubeš and Amir Yehudayoff.  Homogeneous formulas and symmetric polynomials.  Comput. Complexity, 20(3):559–578, 2011.
  * [KdOS19] Mrinal Kumar, Rafael Mendes de Oliveira, and Ramprasad Saptharishi.  Towards optimal depth reductions for syntactically multilinear circuits.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 78:1–78:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [Koi12] Pascal Koiran.  Arithmetic circuits: The chasm at depth four gets wider.  Theor. Comput. Sci., 448:56–65, 2012.
  * [Kos86] S Rao Kosaraju.  Parallel evaluation of division-free arithmetic equations.  In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 231–239, 1986.
  * [KSS14] Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi.  A super-polynomial lower bound for regular arithmetic formulas.  In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 146–153. ACM, 2014.
  * [LST21a] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas.  Superpolynomial lower bounds against low-depth algebraic circuits.  Electron. Colloquium Comput. Complex., TR21-081, 2021.
  * [LST21b] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas.  Superpolynomial lower bounds against low-depth algebraic circuits.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 804–814. IEEE, 2021.
  * [Nis91] Noam Nisan.  Lower bounds for non-commutative computation.  In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 410–418, 1991.
  * [NW97] Noam Nisan and Avi Wigderson.  Lower bounds on arithmetic circuits via partial derivatives.  Computational Complexity, 6(3):217–234, 1997.
  * [PM75] Franco P. Preparata and David E. Muller.  The time required to evaluate division-free arithmetic expressions.  Inf. Process. Lett., 3(5):144–146, 1975.
  * [PM76] Franco P. Preparata and David E. Muller.  Efficient parallel evaluation of boolean expression.  IEEE Trans. Computers, 25(5):548–549, 1976.
  * [Raz06] Ran Raz.  Separation of multilinear circuit and formula size.  Theory of Computing, 2(1):121–135, 2006.
  * [Raz13] Ran Raz.  Tensor-rank and lower bounds for arithmetic formulas.  Journal of the ACM, 60(6):40:1–40:15, 2013.
  * [RY08] Ran Raz and Amir Yehudayoff.  Balancing syntactically multilinear arithmetic circuits.  Computational Complexity, 17(4):515–535, 2008.
  * [Sap15] Ramprasad Saptharishi.  A survey of lower bounds in arithmetic circuit complexity.  Github survey, 2015.
  * [Spi71] Philip M. Spira.  On time hardware complexity tradeoffs for Boolean functions.  In Shu Lin, editor, Proceedings of the Fourth Hawaii International Conference on System Sciences, pages 525–527. Western Periodicals Company, North Hollywood, California, 1971.
  * [SS80] Eli Shamir and Marc Snir.  On the depth complexity of formulas.  Math. Syst. Theory, 13:301–322, 1980.
  * [SW01] Amir Shpilka and Avi Wigderson.  Depth-3 arithmetic circuits over fields of characteristic zero.  Computational Complexity, 10(1):1–27, 2001.
  * [SY10] Amir Shpilka and Amir Yehudayoff.  Arithmetic circuits: A survey of recent results and open questions.  Foundations and Trends in Theoretical Computer Science, 5:207–388, March 2010.
  * [Tav15] Sébastien Tavenas.  Improved bounds for reduction to depth 4 and depth 3.  Information and Computation, 240:2–11, 2015.
  * [TLS22] Sébastien Tavenas, Nutan Limaye, and Srikanth Srinivasan.  Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication.  In STOC, pages 416–425. ACM, 2022.
  * [VSBR83] Leslie G. Valiant, Sven Skyum, Stuart J. Berkowitz, and Charles Rackoff.  Fast Parallel Computation of Polynomials Using Few Processors.  SIAM Journal of Computing, 12(4):641–644, 1983.
  * [YK68] SV Yablonskii and VP Kozyrev.  Mathematical problems of cybernetics.  Information Materials of Scientific Council of Akad. Nauk SSSR on Complex Problem “Kibernetika, 19:3–15, 1968.

##  Appendix A The Bonet-Buss depth-reduction

In this section, we give a proof of Theorem 10. This is essentially the same
proof as in the work of Bonet and Buss [BB94], but since the results in that
paper are only stated for Boolean formulas, we give the proof here for
completeness.

We show that for some large enough absolute constant $C>0$, any polynomial $P$
computed by a formula $F$ of size $s$ can also be computed by a formula
$F^{\prime}$ of size at most $s^{1+\varepsilon}$, depth at most
$2^{O(1/\varepsilon)}\cdot\log s$, and fan-in $2$. Further, if $F$ is
homogeneous/monotone/non-commutative, then so is $F^{\prime}$. This latter
claim will follow directly from the construction.

We assume here that each gate in $F$ has fan-in $2$ to begin with. We can make
this modification to $F$ in the beginning at the expense of increasing the
depth, and without increasing the size.

We prove the claim by induction on the size $s$ of the formula. Let $T(s)$ and
$D(s)$ denote the maximum size and depth (respectively) of $F^{\prime}$ thus
obtained, assuming that $F$ has size at most $s.$ Let $k=2^{C/\varepsilon}$
where $C>0$ is an absolute constant we will choose below. We assume throughout
that $\varepsilon<1$, which is without loss of generality.

The base case of the formula is when $s\leq k,$ in which case the claim is
trivial, as any formula of size $s$ has depth at most $s$, which in this case
is at most $2^{C/\varepsilon}.$

Now, assume that $s>k.$ In this case, we find a gate $\alpha$ such that the
size of the subformula $F_{\alpha}$ rooted at $\alpha$ has size at least
$s-s/k$, while the children $\beta$ and $\gamma$ of $\alpha$ do not satisfy
this property. It is easy to observe that there is a unique $\alpha$ with this
property. Let $*$ denote the operation (either $+$ or $\times$) labelling
$\alpha.$

We replace $\alpha$ by a fresh variable $y$ in $F$ to get a formula $F_{y}$.
Note that $F_{y}$ has size at most $s_{1}=\frac{2s}{k}.$ Since $F_{y}$ has at
most one occurrence of $y$, we can write

$F_{y}=A\cdot y\cdot B+C$

where $A$ is the product of all subformulas that multiply $y$ on the left in
$F$ along the path to the output, $B$ is similarly the product of all
subformulas that multiply $y$ on the right, and $C$ is the polynomial computed
by $F_{y}$ when we set $y$ to $0$. Clearly, $A$, $B$ and $C$ have formulas
$F_{A},F_{B}$ and $F_{C}$ of size at most $s_{1}$. Finally, we get the formula
$F^{\prime}$ as in Figure 1.

$+$$\times$$F_{C}^{\prime}$$\times$$F_{B}^{\prime}$$F_{A}^{\prime}$$*$$F_{\beta}^{\prime}$$F_{\gamma}^{\prime}$
Figure 1: Constructing $F^{\prime}$

Here,
$F_{A}^{\prime},F_{B}^{\prime},F_{C}^{\prime},F_{\beta}^{\prime},F_{\gamma}^{\prime}$
are the formulas obtained by recursively applying the same procedure to
$F_{A},F_{B},F_{C},F_{\beta},F_{\gamma}$.

We can bound the size and depth of the depth-reduced formula by induction. We
have

$D(s)\leq D(s-s/k)+O(1)$

leading easily to an overall depth bound of $O(k\log
s)=2^{O(1/\varepsilon)}\cdot\log s$ for any choice of the constant $C$.

For the size, we have the following recursion.

$T(s)\leq\max_{\begin{subarray}{c}s_{\beta},s_{\gamma},s_{1}:\\\
s_{\beta},s_{\gamma}\leq s(1-1/k)\\\ s_{1}\leq 2s/k\\\
s_{\beta}+s_{\gamma}+s_{1}\leq
s\end{subarray}}T(s_{\beta})+T(s_{\gamma})+3T(s_{1})$

where $s_{\beta}$ and $s_{\gamma}$ are the sizes of $F_{\beta}$ and
$F_{\gamma}$ respectively. We now use induction to bound $T(s)$ as follows.
(We omit the conditions on $s_{\beta},s_{\gamma}$ and $s_{1}$ for notational
simplicity.)

$\displaystyle T(s)$
$\displaystyle\leq\max_{s_{\beta},s_{\gamma},s_{1}}s_{\beta}^{1+\varepsilon}+s_{\gamma}^{1+\varepsilon}+3s_{1}^{1+\varepsilon}$
$\displaystyle\leq\left(s\left(1-\frac{1}{k}\right)\right)^{1+\varepsilon}+\left(\frac{s}{k}\right)^{1+\varepsilon}+3\left(\frac{2s}{k}\right)^{1+\varepsilon}$

where we used the fact that $s_{1}\leq 2s/k$ and the fact that, using the
convexity of the map $x\mapsto x^{1+\varepsilon},$ the function
$s_{\beta}^{1+\varepsilon}+s_{\gamma}^{1+\varepsilon}$ is maximized when
$\max\\{s_{\beta},s_{\gamma}\\}=s-s/k$, meaning that
$\min\\{s_{\beta},s_{\gamma}\\}\leq s/k.$

Continuing the computation, we get

$\displaystyle T(s)\leq
s^{1+\varepsilon}\left(\left(1-\frac{1}{k}\right)+\frac{1}{k^{1+\varepsilon}}+3\frac{4}{k^{1+\varepsilon}}\right)\leq
s^{1+\varepsilon}\cdot\left(1-\frac{1}{k}+\frac{C^{\prime}}{k^{1+\varepsilon}}\right)$

for some large enough absolute constant $C^{\prime}$. Setting
$k=2^{C/\varepsilon}$ for a large enough absolute constant $C$ gives us
$T(s)\leq s^{1+\varepsilon}$, proving the inductive claim.