Improved Low-Depth Set-Multilinear Circuit Lower Bounds

An algebraic circuit over a field $\mathbb{F}$ for a multivariate polynomial $P(x_{1},\ldots,x_{N})$ is a directed acyclic graph (DAG) whose internal vertices (called gates) are labeled as either $+$ (sum) or $\times$ (product), and leaves (vertices of in-degree zero) are labeled by the variables $x_{i}$ or constants from $\mathbb{F}$. A special output gate (the root of the DAG) represents the polynomial $P$. If the DAG happens to be a tree, such a resulting circuit is called an algebraic formula. The size of a circuit is the number of nodes in the DAG. We also consider the product-depth of the circuit, which is the maximum number of product gates on a root-to-leaf path.

An algebraic circuit is therefore a computational model, which solves the computational task of evaluating $P$ on a given input $(x_{1},\ldots,x_{N})$. The complexity of this model is measured by the size of the circuit, which serves as an indicator of the time complexity of computing the polynomial. The product-depth measures the degree to which this computation can be made parallel. As an algebraic circuit is supposed to construct a formal polynomial $P$, it is a syntactic model of computation. This is unlike a Boolean circuit, which is only required to model specific truth-table constraints. The problem of proving algebraic circuit lower bounds is therefore widely considered to be easier than its Boolean counterpart. Indeed, we know that proving VP $\neq$ VNP, the algebraic analog of the P vs. NP problem, is implied by the latter separation, in the non-uniform setting ([Bür00]). We refer the reader to [Sap15] for a much more elaborate survey of this topic.

Much like in the Boolean setting, the problem of showing lower bounds for general algebraic circuits (or even formulas) has remained elusive. However, some remarkable progress has been made very recently by Limaye, Srinivasan, and Tavenas ([LST21]) who in a spectacular breakthrough, showed the first super-polynomial lower bounds for algebraic circuits of all constant depths. Prior to their work, the best known lower bound ([KST16]) even for product-depth 1 (or $\Sigma\Pi\Sigma$ circuits) was only almost-cubic. This is in stark contrast with the Boolean setting, in which we have known strong constant-depth lower bounds for many decades [Ajt83, FSS84, Yao85, Hås86, Raz87, Smo87]. Constant-depth circuits are critical to the study of algebraic complexity theory, as unlike the Boolean setting, strong enough bounds against them are known to yield VP $\neq$ VNP ([AV08]). This helps put into perspective the importance of the work [LST21].

The crucial step in the proof of their result is to first establish super-polynomial lower bounds for a certain restricted class of (low-depth) algebraic circuits, namely set-multilinear circuits which we now define along with other important circuit models. A polynomial is said to be homogeneous if each monomial has the same total degree and multilinear if every variable occurs at most once in any monomial. Now, suppose that the underlying variable set is partitioned into $d$ sets $X_{1},\ldots,X_{d}$. Then the polynomial is said to be set-multilinear with respect to this variable partition if each monomial in $P$ has exactly one variable from each set. We also define different models of computation corresponding to these variants of polynomials classes. An algebraic formula (circuit) is set-multilinear with respect to a variable partition $(X_{1},\ldots,X_{d})$ if each internal node in the formula (circuit) computes a set-multilinear polynomial. Multilinear/homogeneous circuits and formulas are defined analogously.

Several well-studied and interesting polynomials happen to be set-multilinear. For example, the Determinant and the Permanent polynomials, the study of which is profoundly consequential to the field of algebraic complexity theory, are set-multilinear (with respect to the column variables). Another well-studied polynomial, namely the Iterated Matrix Multiplication polynomial, is also set-multilinear. The polynomial IMM_n,d is defined on $N=dn^{2}$ variables, where the variables are partitioned into $d$ sets $X_{1},\ldots,X_{d}$ of size $n^{2}$, each of which is represented as an $n\times n$ matrix with distinct variable entries. The polynomial IMM_n,d is defined to be the polynomial that is the $(1,1)$-th entry of the product matrix $X_{1}X_{2}\cdots X_{d}$. This polynomial has a simple divide-and-conquer-based set-multilinear formula of size $n^{O(\log d)}$, and more generally for every $\Delta\leq\log d$, a set-multilinear formula of product-depth $\Delta$ and size $n^{O(\Delta d^{1/\Delta})}$, and circuit¹¹1In this paper, when speaking of constant-depth models of computation at a high level, we shall often use the terms circuit and formula interchangeably as a product-depth $\Delta$ circuit of size $s$ can be simulated by a product-depth $\Delta$ formula of size $s^{2\Delta}$. of size $n^{O(d^{1/\Delta})}$. Even without the set-multilinearity constraint, no significantly better upper bound is known. It is reasonable to conjecture that this simple upper bound is tight up to the constant in the exponent.

The lower bounds in [LST21] for general constant-depth algebraic circuits are shown in the following sequence of steps:

1. 1.

   It is shown that general low-depth algebraic circuits can be transformed to set-multilinear algebraic circuits of low depth, and without much of a blow-up in size (as long as the degree is small). More precisely, any product-depth $\Delta$ circuit of size $s$ computing a polynomial that is set-multilinear with respect to the partition $(X_{1},\ldots,X_{d})$ where each $|X_{i}|\leq n$, can be converted to a set-multilinear circuit²²2There is also an intermediate ‘homogenization’ step which we skip describing here for the sake of brevity. of product-depth $2\Delta$ and size $\mathrm{poly}(s)\cdot d^{O(d)}$. Such a ‘set-multilinearization’ of general formulas of small degree was already shown before in [Raz13] (which we describe soon in more detail); however, the main contribution of [LST21] here is to prove this depth-preserving version of it.

2. 2.

   Strong lower bounds are then established for low-depth set-multilinear circuits (of small enough degree). More precisely, any set-multilinear circuit $C$ computing IMM_n,d (where $d=O(\log n)$) of product-depth $\Delta$ must have size at least $n^{d^{\exp(-O(\Delta))}}$. This combined with the first step yields the desired lower bound for general constant-depth circuits.

Given Raz’s set-multilinearization of formulas of small degree that we alluded to, and this description of the set-multilinear formula lower bounds from [LST21] when $d=O(\log n)$, it is evident the ‘small degree’ regime is inherently interesting to study - as it provides an avenue, via ‘hardness escalation’, for tackling one of the grand challenges of algebraic complexity theory, namely proving super-polynomial lower bounds for general algebraic formulas. However, we shall now see that even the large degree regime can be equally consequential in this regard.

Consider a polynomial $P$ that is set-multilinear with respect to the variable partition $(X_{1},\ldots,X_{d})$ where each $|X_{i}|\leq n$. The main focus of this paper is to study set-multilinear circuit complexity in the regime where $d$ and $n$ are polynomially related (as opposed to say, the assumption $d=O(\log n)$ described above). We now provide some background and motivation for studying this regime.

In follow-up work [LST22], the same authors showed the first super-polynomial lower bound against unbounded-depth set-multilinear formulas computing IMM_n,n³³3Note that for IMM_n,n, each $X_{i}$ has size $n^{2}$, not $n$. But the important thing for us here is that the degree, $n$, is polynomially related to this parameter.. As is astutely described in [LST22], studying the set-multilinear formula complexity of IMM is extremely interesting and consequential even in the setting $d=n$ because of the following reasons:

• •

  IMM_n,n is a self-reducible polynomial i.e., it is possible to construct formulas for IMM_n,n by recursively using formulas for IMM_n,d (for any $d<n$). In particular, if we had formulas of size $n^{o(\log d)}$ for IMM_n,d (for some $d<n$), this would imply formulas of size $n^{o(\log n)}$ for IMM_n,n. In other words, an optimal $n^{\Omega(\log n)}$ lower bound for IMM_n,n implies $n^{\omega_{d}(1)}$ lower bounds for IMM_n,d for any $d<n$.

• •

  Raz in [Raz13] showed that if an $N$-variate set-multilinear polynomial of degree $d$ has an algebraic formula of size $s$, then it also has a set-multilinear formula of size $\mathrm{poly}(s)\cdot(\log s)^{d}$. In particular, for a set-multilinear polynomial $P$ of degree $d=O(\log N/\log\log N)$, it follows that $P$ has a formula of size $\mathrm{poly}(N)$ if and only if $P$ has a set-multilinear formula of size $\mathrm{poly}(N)$. Thus, having $N^{\omega_{d}(1)}$ set-multilinear formula size lower bounds for such a low degree would imply super-polynomial lower bounds for general formulas.

In particular, proving the optimal $n^{\Omega(\log n)}$ set-multilinear formula size lower bound for IMM_n,n would have dramatic consequences. To this end, the authors in [LST22] are able to show a weaker bound of the form $(\log n)^{\Omega(\log n)}$ instead. Even though it is the case that ‘simply’ improving the base of this exponent from $\log n$ to $n$ yields general formula lower bounds, it seems that we are still far from achieving it. Indeed, as is observed in [LST22], we do not even have the optimal $n^{\Omega(\sqrt{n})}$ lower bound⁴⁴4This is known for set-multilinear (and even multilinear) $\Sigma\Pi\Sigma\Pi$ circuits (see [FLMS15, KST18]), but those are only special cases of general product-depth $2$ circuits, which are $\Sigma\Pi\Sigma\Pi\Sigma$. when product-depth $\Delta=2$. Moreover, we do not know how to obtain a lower bound of the form $n^{\Omega(\sqrt{n})}$ for product-depth $2$ set-multilinear circuits for any explicit polynomial of degree $n$ and in $\mathrm{poly}(n)$ variables. For product-depths $\Delta\leq\log n$, [LST22] shows a set-multilinear formula size lower bound of $(\log n)^{\Omega(\Delta n^{1/\Delta})}$ for IMM_n,n, which is in fact the best set-multilinear lower bound we know for any polynomial of degree $n$ and in $\mathrm{poly}(n)$ variables, and for any $\Delta\geq 2$. As far as we know, the previous best lower bound of $\exp(\Omega(n^{1/\Delta}))$, also for IMM_n,n, followed from the work of Nisan and Wigderson ([NW97]). It is therefore an interesting challenge to improve the base of this exponent from $\log n$ to $n$ i.e., establish a near-optimal $n^{\Omega(n^{1/\Delta})}$ lower bound in the constant (or low) depth setting.

In this paper, we obtain these “optimal” lower bounds, albeit not for IMM_n,n, but rather for another explicit polynomial in VNP. We show the following:

Notice that obtaining this precise bound is interesting also when viewed through the lens of depth reduction. Tavenas ([Tav15]), building on several prior works ([AV08, Koi12]), showed that any algebraic circuit of $\mathrm{poly}(N)$ size computing a homogeneous $N$-variate polynomial of degree $d$ can be converted to a homogeneous circuit of product-depth⁵⁵5The result is stated in [Tav15] for $\Sigma\Pi\Sigma\Pi$ circuits but the proof can be appropriately modified for larger product-depths. $\Delta$ of size $(Nd)^{O(d^{1/\Delta})}$. It easily follows from the proof that this depth reduction preserves syntactic restrictions. That is, if we start with a syntactically set-multilinear circuit, the resulting product-depth $\Delta$ circuit is also syntactically set-multilinear. Therefore, the precise bound in Theorem 1 is sharp in the sense that any asymptotic improvement in its exponent would imply super-polynomial set-multilinear circuit lower bounds, which would be quite a strong and interesting consequence. Another very intriguing direction is to consider the problem of improved depth reduction for set-multilinear circuits. If an asymptotic improvement in the exponent on the bound for general circuits from [Tav15] could be shown to hold for set-multilinear circuits in the setting of Theorem 1 (i.e., when $N=d^{2}$), this would again imply super-polynomial set-multilinear circuit lower bounds. There is some evidence towards this possibility, as [KOS19] shows such an improvement in a certain regime of parameters for multilinear circuits (see the discussion in Section 4 for more details).

We also remark that in several lower bounds for algebraic circuit classes in the past, the lower bound was initially shown for a polynomial in VNP and then with additional effort, was shown to also hold for a polynomial in VP (in particular, the IMM polynomial). A strong candidate for the choice of this polynomial family in VNP has been the Nisan-Wigderson (NW) design-based ([NW94]) family of polynomials. For instance, [KSS14] showed a lower bound of $n^{\Omega(\sqrt{n})}$ for the top fan-in of a $\Sigma\Pi^{[O(\sqrt{n})]}\Sigma\Pi^{[\sqrt{n}]}$ circuit computing the NW polynomial, which was subsequently shown for IMM by [FLMS15]. Similarly, [KLSS17] showed an $n^{\Omega(\sqrt{d})}$ size lower bound for homogeneous depth-4 algebraic formulas for the NW polynomial, which was then shown for IMM later in [KS17]. Much like these examples, our hard polynomial family in Theorem 1 is also indeed the NW polynomial family, as we shall see in Section 3. Our motivation to study constant-depth set-multilinear formula complexity was to prove the optimal lower bounds for the IMM polynomial. Although we are presently able to show it only for the NW polynomial instead of IMM, we are hopeful that this is an important step in its direction.

In addition to our lower bound for bounded-depth set-multilinear formulas, we observe that the same proof technique also implies a lower bound of the form $n^{\Omega(\log n)}$ for unbounded-depth set-multilinear formulas. [LST22] showed a weaker bound of the form $(\log n)^{\Omega(\log n)}$ but for IMM_n,n.

The hard polynomial in Theorem 2 is also the NW polynomial, which if ‘improved’ to IMM_n,n, then as discussed, would yield super-polynomial general formula lower bounds. However, we note that in this case, our result is in some sense subsumed by the result of Raz ([Raz09]) who showed an $n^{\Omega(\log n)}$ lower bound for the $n\times n$ permanent (or determinant) polynomial for unbounded-depth multilinear formulas.

In the bounded-depth setting, other than the works [LST21, LST22, NW97] already mentioned, there have been several lower bounds for the class of low-depth multilinear circuits ([RY09, CLS19, CELS18, KNS20]). In the unbounded-depth setting, apart from the works [LST22, Raz09] already mentioned for set-multilinear formulas, there have also been several strong lower bounds of the form $n^{\Omega(\log n)}$ against multilinear formulas ([DMPY12, HY11, KST18]). However, in both settings of depth, several of these works are not even applicable to the set-multilinear setting as the corresponding hard polynomial does not happen to be set-multilinear.

Our overall proof techniques are similar to that of many known lower bounds. We work with a measure that we show to be small for all polynomials computed by small enough set-multilinear formulas (appropriately so in the bounded and unbounded-depth settings) and large for the NW polynomial. These partial derivative measures were introduced by Nisan and Wigderson in [NW97], who used them to prove the constant-depth set-multilinear formula lower bounds we discussed earlier. [LST21, LST22] use a particular variant of this measure and our measure is in turn inspired from these works.

Given a variable partition $(X_{1},\ldots,X_{d})$, we label each set of variables $X_{i}$ as ‘positive’ or ‘negative’ uniformly at random. Let $\mathcal{P}$ and $\mathcal{N}$ denote the set of positive and negative indices respectively, and let $\mathcal{M}^{\mathcal{P}}$ and $\mathcal{M}^{\mathcal{N}}$ denote the sets of all set-multilinear monomials over $\mathcal{P}$ and $\mathcal{N}$ respectively. For a polynomial that is set-multilinear over the given variable partition $(X_{1},\ldots,X_{d})$, our measure then is simply the rank of the ‘partial derivative matrix’ whose rows are indexed by the elements of $\mathcal{M}^{\mathcal{P}}$ and columns indexed by $\mathcal{N}^{\mathcal{P}}$, and the entry of this matrix corresponding to a row $m_{1}$ and a column $m_{2}$ is the coefficient of the monomial $m_{1}\cdot m_{2}$ in the given polynomial.

In contrast, the measure used in [LST21] is deterministic and moreover, it is asymmetric with respect to the positive and negative variable sets, in the sense that while keeping the positive variable sets as is, it first reduces the size of the negative variable sets by arbitrarily setting a few of these variables to field constants, and then works with the resulting polynomial. On the other hand, [LST22] does use a randomized measure, but one that is still asymmetric, relying on randomly setting a few of the variables inside each set to constants. The way they control the discrepancy between the sizes of the positive and negative variable sets (which is indeed crucial for obtaining the claimed lower bounds) is by imposing a Martingale-like distribution. The lower bound of [NW97] also uses random restrictions to enable them to effectively “simplify” the circuit and upper bound its complexity. Our symmetric, randomized measure avoids random restrictions altogether, and though it is inspired by the measure and the techniques from [LST21], it is also reminiscent of the measures used in [Raz09, RY09] to prove multilinear formula lower bounds.