Answers are grounded in this paper and cite their sources.
It is well known that VF = VBP₃ (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 mVBP₂ mVBP₃ … by showing that immk,n requires width w mABPs to have depth at least (k/w-1)^1/2 n1/(w-2) - 1 whenever 3 ≤ 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×, giving a lower bound of n · k^d×(n^1d× - 1) for the iterated matrix multiplication polynomial and ((e+o(1)) ln^∘(d×-1)(n))ⁿ for the permanent.
No takes yet. Share an insight, caveat, or question.
Dörfler et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: