Lower Bounds for Set-Multilinear Branching Programs

The recent celebrated breakthrough work of Limaye, Srinivasan, and Tavenas ([LST21]) establishes super-polynomial lower bounds for general algebraic circuits for all constant-depths, a problem that was open for many decades. In order to show this, it is first shown that general low-depth algebraic formulas can be converted to set-multilinear algebraic formulas of low depth as well, and without much of a blow-up in size (as long as the degree is small). Subsequently, strong lower bounds are established for low-depth set-multilinear circuits (of small enough degree), which when combined with the first step yields the desired lower bound for general constant-depth circuits.

Raz [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. A recent line of work by Kush and Saraf ([KS22, KS23]) can be viewed as an attempt to prove general formula lower bounds via this route.

In fact, in the context of ABPs as well, the very recent work of Bhargav, Dwivedi, and Saxena ([BDS24]) reduces the problem of showing lower bounds against general ABPs to proving lower bounds against sums of ordered set-multlinear ABPs (again, as long as the degree is small enough). Ordered set-multilinear ABPs are, in fact, historically well-studied models and extremely well-understood. However, despite their apparent simplicity, the work [BDS24] implies that understanding their sums – a model that is far less studied – is at the forefront of understanding Valiant’s conjecture. We state their result formally as Theorem 1.5 in Section 1.3.

First however, as this is also the main model considered in this paper, we begin by formally defining ordered set-multilinear ABPs and outlining their importance.

At this point, it is essential to take note of the terminology in this context: in this paper, a general (or “unordered”) set-multilinear branching program refers to an ABP for which each internal node computes a polynomial that is set-multilinear with respect to some subset of the global partition, whereas an ordered set-multilinear branching program is more specialized and has the property that any two nodes in the same layer compute polynomials that are set-multilinear with respect to the same partition.

We have known exponential width lower bounds against a single ordered set-multilinear ABP since the foundational work of Nisan. In [Nis91], he showed that there are explicit polynomials (in fact, in $\mathsf{VP}$) which require any ordered set-multilinear ABP computing them to be of exponentially large width. Viewed differently, this work even shows that in the non-commutative setting, $\mathsf{VBP}\neq\mathsf{VP}$⁶⁶6We briefly explain the connection between ordered set-multilinear ABPs and non-commutative computation in Section 1.4.. More crucially however, this work introduced a powerful technique – a notion known as the partial derivative method – that has been instrumental in the bulk of the major advancements in algebraic complexity theory over the past three decades (such as [NW97, Raz06, RY09, Kay12, KST16, KLSS17, KS17, LST21, TLS22], see also [SY10, Sap15]).

Despite the considerable development of the partial derivative technique over the course of these works (and many more) for proving strong lower bounds against various algebraic models, relatively little is known about a general sum of ordered set-multilinear ABPs – a simple and direct generalization of the original model considered by Nisan. There is some progress in the literature towards this goal but which still requires additional structural restrictions on either the max-width or the support size or the size of each part in the variable partition. The work [AR16] of Arvind and Raja shows that any $\sum\mathrm{smABP}$ of support size $t$ computing the $n\times n$ permanent polynomial requires max-width (and therefore, total-width) at least $2^{\Omega(n/t)}$. Note that for this bound to be super-polynomial, the support size needs to be heavily restricted i.e., $t$ must be sub-linear. On the other hand, the work [BDS24] also shows a super-polynomial lower bound in this context: it implies that no $\sum\mathrm{smABP}$ of polynomially-bounded total-width can compute the iterated matrix multiplication (IMM) polynomial. However, their work requires the additional assumption that the max-width of such an $\sum\mathrm{smABP}$ is $n^{o(1)}$, that is sub-polynomial in the number of variables.

Apart from these, Ramya and Rao ([RR20]) use the partial derivative method to show an exponential lower bound against the related model of sum of ROABPs in the multilinear setting, as well as some other structured multilinear ABPs. Their lower bounds are for a multilinear polynomial that is computable by a small multilinear circuit. Ghoshal and Rao ([GR21]) partially extend their work by proving an exponential lower bound, for a polynomial that is computable even by a small multilinear ABP, against sums of ROABPs that have polynomially bounded width. Notably, these results can be viewed as lower bounds against the $\sum\mathrm{smABP}$ model where each variable set in the variable partition has size $2$ (that is, the total number of variables is $2d$). This is because a multilinear polynomial and any multilinear model computing it (such as circuit, formula, or branching program) can be converted, in a generic manner, to a set-multilinear polynomial and the corresponding set-multilinear model respectively, with each variable set having size $2$ (also see Section 1.5 for a discussion). However, from the perspective of hardness escalation of [BDS24] that is described above – and which is indeed the focus of our work – the setting of $d$ that is far more interesting is when it is allowed to be considerably smaller than $n$. More precisely, the framework of [BDS24] requires $d=O(\log n/\log\log n)$ (stated formally as Theorem 1.5 below). A detailed discussion about the results in [RR20], [GR21] and how they compare with our work can be found in Section 1.5.

The high-level idea is to work with a measure that we show to be “small” for all polynomials computed by a specified model of computation – the model against which we wish to prove lower bounds. If we can also show that there is a “hard” polynomial for which the measure is in fact “large”, then it follows that this polynomial cannot be computed by the specified model. These partial derivative measures, after the initial work ([Nis91]) by Nisan, were further developed by Nisan and Wigderson in [NW97], who used them to prove some constant-depth set-multilinear formula lower bounds. Since then, variations of these measures have also been used to prove various other stronger set-multilinear formula lower bounds (e.g., [LST21, TLS22, LST22, BDS22, KS22, KS23]).

Given a variable partition $(X_{1},\ldots,X_{d})$, the idea is to label each set of variables $X_{i}$ as ‘$+1$’ or ‘$-1$’ according to some rule (called a “word”) $w\in\{-1,1\}^{d}$. Let $\mathcal{P}_{w}$ and $\mathcal{N}_{w}$ denote the set of positive and negative indices (or coordinates) respectively, and let $\mathcal{M}_{w}^{\mathcal{P}}$ and $\mathcal{M}_{w}^{\mathcal{N}}$ denote the sets of all set-multilinear monomials over $\mathcal{P}_{w}$ and $\mathcal{N}_{w}$ respectively. For a polynomial $f$ that is set-multilinear over the given variable partition $(X_{1},\ldots,X_{d})$, the measure then is simply the rank of the “partial derivative matrix” $\mathcal{M}_{w}(f)$, whose rows are indexed by the elements of $\mathcal{M}_{w}^{\mathcal{P}}$ and columns indexed by $\mathcal{M}_{w}^{\mathcal{N}}$, 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 $f$.

For a subset $S\subseteq[d]$, let $w_{S}$ denote the sum of those coordinates of $w$ that lie in $S$. In other words, $|w_{S}|$ measures the amount of “bias” that the rule $w$ exhibits when restricted to the $S$ coordinates. Note that the rank of $M_{w}(f)$ can never exceed $n^{(d-|w_{[d]}|)/{2}}$. Furthermore, we have that the rank measure is multiplicative: if $f$ and $g$ are polynomials that are set-multilinear over disjoint subsets of the global partition $(X_{1},\ldots,X_{d})$, then the rank of $\mathcal{M}_{w}(f\cdot g)$ is the product of the ranks of $\mathcal{M}_{w}(f)$ and $\mathcal{M}_{w}(g)$. These two observations, combined with the sub-additivity of rank, provide a recipe for showing lower bounds against any given set-multilinear model of computation: the overall idea is to carefully split up the original model into smaller, multiplicatively disjoint parts and then argue the existence of a rule for which enough of these parts exhibit high bias. This process allows us to prove that the measure is small for the model of computation. Therefore, one can conclude that any explicit polynomial for which the measure is provably high – which needs to established separately – can not be computed by this model. It is known ([KS22, KS23]) that there is a set-multilinear polynomial $NW_{n,d}$ in $\mathsf{VNP}$ (see Section 2.3) as well as a set-multilinear polynomial $F_{n,d}$ in $\mathsf{VP}$ (see Section 2.4) for which the matrices $\mathcal{M}_{w}(NW_{n,d}),\mathcal{M}_{w}(F_{n,d}),$ have full-rank, whenever $|\mathcal{P}_{w}|=|\mathcal{N}_{w}|$.

Let us first summarize how Nisan’s original partial derivative method from [Nis91], as alluded to in Section 1.2, can be applied in this context to obtain lower bounds against the size of a single ordered set-multilinear ABP (ordered smABP) computing the aforementioned “full-rank” polynomials. Given any set-multilinear branching program $A$ ordered with respect to some permutation $\sigma\in S_{d}$ computing $F_{n,d}$, the idea is to pick a word $w$ such that the $+1$ labels in $w$ precisely correspond to the “left half” of the ordering $\sigma$, and the $-1$ labels correspond to the “right half”. One can then observe that the rank of $\mathcal{M}_{w}(F_{n,d})=\mathcal{M}_{w}(A)$ serves as a lower bound on the number of nodes $s$ in the middle layer of the ABP, yielding a near-optimal $n^{\Omega(d)}$ lower bound: this is because the matrix $\mathcal{M}_{w}(A)$ is easily seen to be the product of an $n^{d/2}\times s$ and an $s\times n^{d/2}$ matrix.

We now sketch an alternate proof: rather than constructing a word dependent on the ordering of variable sets $X_{i}$ in the ordered smABP $A$ as above, choose a uniformly random⁹⁹9We also need to suitably condition on the event that the word $w$ is symmetric (i.e., $|\mathcal{P}_{w}|=|\mathcal{N}_{w}|$) in order to use the full-rank property of the hard polynomial – the probability of this event is $\Theta(\frac{1}{\sqrt{d}})$. For ease of exposition, we omit the technical details in this sketch. word $w$ from $\{-1,1\}^{d}$. We demonstrate that, with positive probability, the rank of $\mathcal{M}_{w}(A)$ is bounded by $s\cdot n^{d/2-\Omega(\sqrt{d})}$, where $s$ is the width of the middle layer in $A$: Standard anti-concentration bounds imply that, with at least constant probability, the bias in the left and right halves of $A$ is $\Omega(\sqrt{d})$. Since $A$ can be expressed as a sum of $s$ polynomials $f_{i}\cdot g_{i}$ for $i\in[s]$, where each $f_{i}$ and $g_{i}$ are ordered smABPs with respect to disjoint subsets of the global partition, we encounter a loss of a factor of $n^{\Omega(\sqrt{d})}$ in the rank of the product polynomial $\mathcal{M}_{w}(f_{i}\cdot g_{i})$ due to the bias of $w$. This, combined with the sub-additivity of rank, shows the desired bound of $s\cdot n^{d/2-\Omega(\sqrt{d})}$ on the rank of $\mathcal{M}_{w}(A)$. Finally, we exploit the full-rank property of $F_{n,d}$ with respect to such words to establish a lower bound of $n^{\Omega(\sqrt{d})}$ on the width $s$ of a single ordered smABP computing $F_{n,d}$. Notably, this bound is indeed slightly worse than what one can obtain by manually defining a rule $w$ deterministically, which ensures a maximal bias of $d/2$ in each half of $A$ as described in the paragraph above.

The alternative argument described above yields an exponential lower bound even for a sum of ordered smABPs, assuming the number of summands is small. Consider a $\sum\mathrm{smABP}$ of the form $\sum_{i=1}^{t}A_{i}$, of max-width $s$, computing $F_{n,d}$. For each summand $A_{i}$, the analysis above provides an upper bound of $s\cdot n^{d/2-\Omega(\sqrt{d})}$ on the rank of $\mathcal{M}_{w}(A_{i})$ with constant probability. If the number of summands $t$ is a small enough constant, the union bound ensures the existence of a word $w$ such that the rank of $\mathcal{M}_{w}(\sum A_{i})$ is at most $t\cdot s\cdot n^{d/2-\Omega(\sqrt{d})}$. Thus¹⁰¹⁰10See footnote 9., we obtain an exponential lower bound on $t\cdot s$ since this $\sum\mathrm{smABP}$ computes a full-rank polynomial. However, because of the use of the union bound in this manner, this method faces an inherent limitation – it is unable to handle more than a very small number of summands, even if we lower the bias demand from each half (e.g., from $\Omega(\sqrt{d})$ to $\Omega(\sqrt[4]{d})$ or a smaller polynomial in $d$). In fact, one can construct a sum of $d$ ordered smABPs (by starting with a single smABP ordered arbitrarily and considering the $d$ cyclic shifts of this ordering) such that any unbiased word $w$ (i.e., $w_{[d]}=0$) has the property that for at least one of the summands, the left and right halves will have no bias! Evidently then, in order to prove lower bounds against an unrestricted number of summands, we need another method to analyze the rank of the summands. Nonetheless, a conceptual takeaway from the exercise above is that selecting a rule $w$ that is oblivious to the orderings of individual summands (and in particular, a random rule) still lets us derive strong lower bounds for the sum of multiple ordered smABPs.

Suppose instead of slicing an ordered smABP $A$ down the middle, we slice it into three roughly equal pieces. Then, it is possible to write the polynomial computed by $A$ as a sum over $s^{2}$ terms, each of the form $f_{i}\cdot g_{i}\cdot h_{i}$ where for each $i$, each of $f_{i},g_{i},h_{i}$ depends on $d/3$ disjoint variable sets of the global partition. We can then perform a similar analysis as above to show enough bias across these $3$ pieces, thereby obtaining a rank deficit. More precisely, we can conclude that for a single ordered smABP $A$, again with a constant probability, the rank of $\mathcal{M}_{w}(A)$ is at most $s^{2}\cdot n^{d/2-\Omega(\sqrt{d})}$. When we slice the ABP into $3$ pieces in this way, it is not immediately clear where the gain is. In fact, for a single ordered smABP, this method actually gives a worse lower bound on $s$ due to the presence of the factor of $s^{2}$. Where we gain is in the magnitude of the probability with which we can guarantee that a single ordered smABP has a rank deficit – we will now describe how this observation allows us to take a union bound over many more summands.

In order to illustrate this trade-off more clearly, we will partition the ordered smABP $A$ into many more pieces. Suppose we slice it into $q\approx\sqrt{d}$ pieces, each of size roughly $r=d/q\approx\sqrt{d}$ (this is just one setting of parameters; $q$ and $r$ are suitably optimized in the final proof). Thus, the polynomial that $A$ computes can be written as a sum of at most $s^{q-1}$ terms, where each term is a product of $q$ polynomials – each set-multilinear over a disjoint subset of the global partition, where each piece has size $r$. When a word $w$ is chosen randomly, each such piece again exhibits a bias of about $\Omega(\sqrt{r})$ with constant probability. The crucial observation then is that by known concentration bounds, it can be shown that with probability exponentially close to $1$, the sum of the biases across all the $q$ pieces is $\Omega(q\sqrt{r})=\mathrm{poly}(d)$. For a single ordered smABP $A$, this shows that the rank of $\mathcal{M}_{w}(A)$ is at most $s^{q}\cdot n^{-\Omega(q\sqrt{r})}$, which is still enough to show an exponential lower bound on $s$, even though it is worse than what we obtained by slicing into fewer pieces.

The key advantage in implementing this analysis is that it provides a way to argue that for a random word $w$, $\mathcal{M}_{w}(A)$ has low rank for a single ordered smABP $A$ – with probability exponentially close to $1$. In particular, this allows us to union bound over exponentially many ordered smABPs and show that even if we have an $\sum\mathrm{smABP}$ computing $F_{n,d}$ of exponential support size, with high probability, each summand will have a rank deficit. Then, again using the sub-additivity of rank, we can conclude that the sum has a rank deficit as well.

This method of analyzing the rank of an ordered smABP by partitioning it into numerous pieces and tactfully using concentration bounds is novel, and conceptually the most essential aspect of the proof. As we demonstrated above, this method of analysis indeed gives a worse bound for a single smABP. However, while mildly sacrificing what we can prove about the rank of a single ordered smABP, we are able to leverage it to still prove something meaningful about the rank of a sum with a much larger number of summands.

Our partial derivative measure draws inspiration from previously known lower bounds in the context of multilinear and set-multilinear formulas ([Raz06, KS22]). One noteworthy distinction lies in the analysis of the measure: whereas the partitioning is present intrinsically in those formula settings, in our setting of ABPs, we deliberately introduce the partitioning at the expense of a notable increase in the number of summands or the total-width (and therefore, in the number of events we union bound over). The substantial advantage gained in utilizing this partitioning for rank analysis justifies the tolerable increase in the total-width.

In order to make the hard polynomial in Theorems 1.6 and 1.4 lie in $\mathsf{VBP}$, one might wonder if we can get away with using the same rank measure (i.e., rank of the matrix $M_{w}(\cdot)$ for a uniformly random word $w\in\{-1,1\}^{d}$) that was used in the analysis above for the $\mathsf{VP}$ polynomial $F_{n,d}$. However, as far as we know, full-rank polynomials (in the sense described above) may also require super-polynomial sized set-multilinear ABPs. Thus, in order to prove a separation between (general) set-multilinear ABPs and (sums of) ordered set-multilinear ABPs, we seek a property that is weaker than being full-rank and yet is still useful enough for proving lower bounds against our model. For this, we rely upon the arc-partition framework that is developed in [KS23] in order to prove near-optimal set-multilinear formula lower bounds (building upon the initial ingenious construction given in [DMPY12] for the multilinear context), tailor the framework to our $\sum\mathrm{smABP}$ model, and use a more delicate concentration bound analysis in order to prove our results.

An arc-partition is a special kind of symmetric word $w$ from $\{-1,1\}^{d}$: we will now describe a distribution over $\{-1,1\}^{d}$; the words that will have positive probability of being obtained in this distribution will be called arc-partitions. The distribution is defined according to the following (iterative) sampling algorithm. Position the $d$ variable sets on a cycle with $d$ nodes so that there is an edge between $i$ and $i+1$ modulo $d$. Start with the arc $[L_{1},R_{1}]=\{1,2\}$ (an arc is a connected path on the cycle). At step $t>1$ of the process, maintain a partition of the arc $[L_{t},R_{t}]$. “Grow” this partition by first picking a pair uniformly at random out of the three possible pairs $\{L_{t}-2,L_{t}-1\},\{L_{t}-1,R_{t}+1\},\{R_{t}+1,R_{t}+2\}$, and then choosing a labelling (or partition) $\Pi$ on this pair i.e., assigning one of them ‘$+1$’ and the other ‘$-1$’ uniformly at random. After $d/2$ steps, we have chosen a partition (i.e., a word $w$ from $\{-1,1\}^{d}$) of the $d$ variable sets into two disjoint, equal-size sets of variables $\mathcal{P}$ and $\mathcal{N}$. It is known from [KS23] that there exist set-multilinear polynomials $G_{n,d}$ (as defined in Section 2.5) that are arc-full-rank i.e., $\mathcal{M}_{w}(G_{n,d})$ is full-rank for every arc-partition $w$. Analogous to the proofs of Theorems 1.6 and 1.4, we establish our $\sum\mathrm{smABP}$ lower bounds by showing that with high probability, every $\sum\mathrm{smABP}$ has an appropriately large rank deficit with respect to the arc-partition distribution. However, as we now briefly explain, this analysis turns out to be significantly more intricate.

Similar to the analysis as in the $\mathsf{VP}$ case, we partition an ordered smABP $A$ into $q$ pieces of size $r$ each, and write the polynomial that it computes as a sum of at most $s^{q}$ terms. Again, the task is to show that an arc-partition $w$ exhibits a large total bias across the $q$ pieces: more precisely, we show that if the pieces are labelled as $S_{1},\ldots,S_{q}$, then with probability exponentially close to $1$, the sum $\sum_{i=1}^{q}|w_{S_{i}}|$ (i.e., the total bias of $w$ across these pieces) is $\Omega(qr^{\varepsilon})$, which is polynomially large in $d$ for an appropriate setting of $q,r$. This then yields the desired rank deficit similar to the $\mathsf{VP}$ analysis (albeit with mildly worse parameters).

The bias lower bound is established in the following sequence of steps:

• •

  View the partition $(S_{1},\ldots,S_{q})$ of $[d]$ as a fixed “coloring” of the latter. We say that a pair – as sampled in the construction of an arc-partition described above – “violates” a color $S$ if exactly one of the elements of the pair is colored by the set $S$. Then, we show that with probability exponentially close to $1$, “many” colors must have “many” violations: more precisely, that at least a constant fraction of the colors (i.e., $\Omega(q)$ many) have at least $r^{2\varepsilon}$ many violations each (for some small constant $\varepsilon>0$). Such a “many violations” lemma is also established in [KS23] in the context of proving set-multilinear formula lower bounds. We show that this lemma, in fact, holds for a much wider range of parameters than was previously known; this extension is indeed necessary for our use. The proof of this strengthened many violations lemma is deferred to the appendix.

• •

  We then use the strengthened many violations lemma to argue that even though $w$ is not chosen uniformly at random and as such, its coordinates are not truly independent, it possesses “enough” inherent independence that a similar concentration bound as in the $\mathsf{VP}$ analysis is applicable. More precisely, we show that with high probability, there is an ordering of a set of $\Omega(q)$ colors such that each such color has at least $r^{2\varepsilon}$ violations and a more nuanced application of standard concentration bounds shows that $w$ exhibits a total bias of at least $\Omega(qr^{\varepsilon})$.