REVIEW
A Width Hierarchy of Monotone Algebraic Branching Programs
Computational Complexity · Submitted 4 Nov 2026 · 20 references
Pith's verdict: A real and new width hierarchy for mABPs; two repairable display errors, and the Decomposition Lemma is the step a referee should scrutinize.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Monotone algebraic branching programs form an infinite strict hierarchy by width, and the proof gives an explicit depth lower bound for the iterated matrix multiplication polynomial.
The reading
What carries the argument
The proof counts monomials: it measures a polynomial by the size of its support and applies that measure to the set-multilinear polynomial $\mathrm{imm}_{k,n}$, whose monomials are exactly the entry-$(1,1)$ products arising from walks through $n$ matrices. Two lemmas carry the recursion. The Decomposition Lemma (Lemma 4.5) shows that any width-$w$ mABP computing more than $w \cdot k^{n-2}$ monomials of $\mathrm{imm}_{k,n}$ must contain, in every layer, a node $v$ whose prefix polynomial $f_{s\to v}$ or suffix polynomial $f_{v\to t}$ is a constant; these nodes trace two constant paths along which the program splits into fewer than $d^2$ sub-programs of width $w-1$. The Densification Lemma (Lemma 4.7) then restores the fraction of monomials lost in the split: it projects the decomposed pieces onto a smaller $\mathrm{imm}_{k,m}$ whose support keeps a large enough share to re-enter the decomposition. Iterating this width reduction down to the base case — width-2 mABPs produce at most $2^{n-1}$ monomials while $\mathrm{imm}_{3,n}$ has $3^{n-1}$ — yields the depth lower bound. Independently, the paper generalizes a weight-function framework for monotone formulas to bounded multiplication depth, capping the 'relevant' weight at every sub-formula through a dynamic-programming function $W(n,s,d^{\times})$; that framework yields the tight leaf counts for $\mathrm{imm}_{k,n}$ and the permanent.
Extended reading notes
Core claim
The central discovery, on the paper's own terms, is Theorem 4.8: for $3 \le w < k$, any width-$w$ monotone algebraic branching program computing a polynomial $f$ with $\operatorname{supp}(f) = \operatorname{supp}(\mathrm{imm}_{k,n})$ requires depth at least $\left(\frac{k}{w-1}\right)^{\frac{1}{2}\left\lfloor n^{1/(w-2)}\right\rfloor - 1}$. Since $\mathrm{imm}_{k,n}$ itself is computable in width $k$ and depth $n$, the bound yields the strict inclusion $\mathrm{mVBP}_w \subsetneq \mathrm{mVBP}_k$ for every $1 \le w < k$, hence an infinite constant-width hierarchy together with separations of classes whose widths grow slowly with $n$. The same machinery sharpens the position of monotone formulas relative to the hierarchy: $\mathrm{mVBP}_{O(1)} \subsetneq \mathrm{mVF} \subsetneq \mathrm{mVBP}_{O(\log n)}$, with $\mathrm{mVF}$ incomparable to $\mathrm{mVBP}_{k(n)}$ for $k(n) \in o(\log n/(\log \log n)^2)$. A second contribution generalizes the classical leaf-counting framework for monotone formulas to bounded multiplication depth $d^{\times}$, giving the tight leaf bounds $n \cdot k^{d^{\times}(n^{1/d^{\times}}-1)}$ for $\mathrm{imm}_{k,n}$ and $\left((e+o(1)) \ln^{\circ(d^{\times}-1)}(n)\right)^n$ for the permanent.
Load-bearing premise
The entire hierarchy rests on the Decomposition Lemma's structural claim that in every layer of a width-$w$ mABP computing a sufficiently large fraction of $\mathrm{imm}_{k,n}$, some node has a constant prefix or suffix polynomial; if variables from one matrix block could instead appear on both sides of every node, the per-layer monomial cap of $w \cdot k^{n-2}$ and the whole width-reduction recursion would fail.
Editorial extensions
If this is right
- Every extra register strictly strengthens the model: $\mathrm{mVBP}_w \subsetneq \mathrm{mVBP}_k$ for all $1 \le w < k$, an infinite hierarchy with no analogue in the non-monotone setting.
- Slowly growing widths are also separated: if $w(n)$ stays below about $\log n / \log \log n$ (with an allowed constant smaller than 1) and $k(n)$ exceeds $w(n)$ by a constant factor, then $\mathrm{mVBP}_{w(n)} \subsetneq \mathrm{mVBP}_{k(n)}$ with superpolynomial depth gaps.
- Monotone formulas sit strictly between constant-width and logarithmic-width mABPs, and are incomparable with mABPs whose width grows slowly; in particular $\mathrm{mVBP}_{O(1)} \subsetneq \mathrm{mVF} \subsetneq \mathrm{mVBP}_{O(\log n)}$.
- The fixed-depth formula hierarchy and the fixed-width mABP hierarchy are tightly coupled: polynomial-size depth-$2d$ monotone formulas escape width-$d-1$ mABPs, while width $2\lceil d/2\rceil + 1$ suffices to simulate all polynomial-size depth-$d$ monotone formulas.
- Bounded multiplication depth is a genuine bottleneck for monotone formulas: $\mathrm{imm}_{k,n}$ needs $n \cdot k^{d^{\times}(n^{1/d^{\times}}-1)}$ leaves, the $n \times n$ permanent needs $\left((e+o(1)) \ln^{\circ(d^{\times}-1)}(n)\right)^n$ leaves, and both bounds are tight up to rounding.
Reading between the lines
- The exactness of the depth bound suggests a general recipe for register-based monotone models: a set-multilinear test polynomial plus a per-layer monomial cap forces a strict width hierarchy whenever the model cannot cancel, so monotone analogues of other width parameters (treewidth- or pathwidth-based circuit measures) are plausible next targets.
- The Decomposition Lemma's 'two-legged' structure — every layer of a sufficiently wide and shallow monotone computation has a node through which prefix and suffix factorize by constants — may be a property of shallow monotone computations in general, not just of $\mathrm{imm}_{k,n}$; testing it on other set-multilinear families would show how far the technique extends.
- The Densification Lemma is a monomial-density booster that is independent of the branching-program model and could be reused to transfer support-fraction bounds between different sizes of the same set-multilinear family in other lower-bound proofs.
- The width-depth tradeoff of Theorem 8.4 leaves a gap against the lower bound; a natural next step would be a computational search for small $k$, $n$, $w$ to see whether the true depth requirement of $\mathrm{imm}_{k,n}$ sits near the lower or the upper end.
Original abstract
It is well known that $\mathsf{VF} = \mathsf{VBP}_{3}$ (Ben-Or-Cleve'92), i.e. the width of any constant-width algebraic branching program can be reduced to width $3$ with only a polynomial overhead to size. We prove that this is not the case for the monotone equivalents. In particular, we prove that there is an infinite hierarchy $\mathsf{mVBP}_{2} \subsetneq \mathsf{mVBP}_{3} \subsetneq \ldots$ by showing that $\mathrm{imm}_{k,n}$ requires width $w$ mABPs to have depth at least $\left(\frac{k}{w-1}\right)^{\frac{1}{2}\left\lfloor n^{\frac{1}{(w-2)}} \right\rfloor - 1}$ whenever $3 \leq w < k$. We prove this lower bound using support-based techniques. Since this lower bound is exact instead of asymptotic, it allows some width separations even for superconstant width. Moreover, it allows us to show that the expressive power of poly-sized monotone formulas of depth $2d$ is not reached by poly-sized mABPs of width $d-1$ but a width of $2d+1$ is sufficient. We contrast this to unbounded-depth monotone formulas, which are proven to be stronger than constant-width mABPs, but weaker than $\log$-width mABPs and incomparable for most widths in between. Finally, we generalize Snir's framework (Snir'80) for showing lower bounds on the number of leaves of monotone formulas to monotone formulas of multiplication depth $d^{\times}$, giving a lower bound of $n \cdot k^{d^{\times}(n^{\frac{1}{d^{\times}}} - 1)}$ for the iterated matrix multiplication polynomial and $\left(\left(e+o(1)\right) \ln^{\circ(d^{\times}-1)}(n)\right)^n$ for the permanent.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
It is well known that $\mathsf{VF} = \mathsf{VBP}_{3}$ (Ben-Or-Cleve'92), i.e. the width of any constant-width algebraic branching program can be reduced to width $3$ with only a polynomial overhead to size. We prove that this is not the case for the monotone equivalents. In particular, we prove that there is an infinite hierarchy $\mathsf{mVBP}_{2} \subsetneq \mathsf{mVBP}_{3} \subsetneq \ldots$ by showing that $\mathrm{imm}_{k,n}$ requires width $w$ mABPs to have depth at least $\left(\frac{k}{w-1}\right)^{\frac{1}{2}\left\lfloor n^{\frac{1}{(w-2)}} \right\rfloor - 1}$ whenever $3 \leq w < k$. We prove this lower bound using support-based techniques. Since this lower bound is exact instead of asymptotic, it allows some width separations even for superconstant width. Moreover, it allows us to show that the expressive power of poly-sized monotone formulas of depth $2d$ is not reached by poly-sized mABPs of width $d-1$ but a width of $2d+1$ is sufficient. We contrast this to unbounded-depth monotone formulas, which are proven to be stronger than constant-width mABPs, but weaker than $\log$-width mABPs and incomparable for most widths in between. Finally, we generalize Snir's framework (Snir'80) for showing lower bounds on the number of leaves of monotone formulas to monotone formulas of multiplication depth $d^{\times}$, giving a lower bound of $n \cdot k^{d^{\times}(n^{\frac{1}{d^{\times}}} - 1)}$ for the iterated matrix multiplication polynomial and $\left(\left(e+o(1)\right) \ln^{\circ(d^{\times}-1)}(n)\right)^n$ for the permanent.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | It is well known that $\mathsf{VF} = \mathsf{VBP}_{3}$ (Ben-Or-Cleve'92), i.e. the width of any constant-width algebraic branching program can be reduced to width $3$ with only a polynomial overhead to size. | background 1.00 | 0.03 | 0.03 | asserted 1.00 |
| s1 | We prove that this is not the case for the monotone equivalents. | contribution 0.50 | 0.69 | 0.63 | asserted 1.00 |
| s2 | In particular, we prove that there is an infinite hierarchy $\mathsf{mVBP}_{2} \subsetneq \mathsf{mVBP}_{3} \subsetneq \ldots$ by showing that $\mathrm{imm}_{k,n}$ requires width $w$ mABPs to have depth at least $\left(\frac{k}{w-1}\right)^{\frac{1}{2}\left\lfloor n^{\frac{1}{(w-2)}} \right\rfloor - 1}$ whenever $3 \leq w < k$. | result 0.89 | 0.97 | 0.84 | asserted 1.00 |
| s3 | We prove this lower bound using support-based techniques. | method 1.00 | 0.93 | 0.03 | asserted 1.00 |
| s4 | Since this lower bound is exact instead of asymptotic, it allows some width separations even for superconstant width. | interpretation 0.93 | 0.86 | 0.07 | asserted 0.95 |
| s5 | Moreover, it allows us to show that the expressive power of poly-sized monotone formulas of depth $2d$ is not reached by poly-sized mABPs of width $d-1$ but a width of $2d+1$ is sufficient. | result 0.96 | 0.93 | 0.10 | asserted 1.00 |
| s6 | We contrast this to unbounded-depth monotone formulas, which are proven to be stronger than constant-width mABPs, but weaker than $\log$-width mABPs and incomparable for most widths in between. | result 0.89 | 0.74 | 0.07 | asserted 1.00 |
| s7 | Finally, we generalize Snir's framework (Snir'80) for showing lower bounds on the number of leaves of monotone formulas to monotone formulas of multiplication depth $d^{\times}$, giving a lower bound of $n \cdot k^{d^{\times}(n^{\frac{1}{d^{\times}}} - 1)}$ for the iterated matrix multiplication polynomial and $\left(\left(e+o(1)\right) \ln^{\circ(d^{\times}-1)}(n)\right)^n$ for the permanent. | contribution 0.57 | 0.89 | 0.08 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2611.06608 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.