Theorem 8.4 — narrow mABP construction
OpenMonoABPWidth.Hierarchy.Supplement.theorem_8_4algebraic-complexitymonotone-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For integers , , and every integer , set
There exists a real monotone branching program , with singleton source and sink layers, computing such that
The parameter range guarantees . All lengths and matrix dimensions are included, along with . The depth bound keeps its exact front factor and nested rounding. This companion theorem supplies a width-depth upper tradeoff.
Differences from the source:
- encoding: floor and ceiling divisions and width w → natural floor division for q, real ceiling for b, and width at most w in the full published MABP model; reason: the allowed parameter range gives q≥1 and r≥1, so all denominators are positive; width is an upper bound as in the construction
Preamble
import Definitions.Def_MonoABPWidth_Hierarchy_branchingProgram import Definitions.Def_SetMultCost_imm open scoped BigOperators ENNReal
Formal statement
namespace MonoABPWidth.Hierarchy.Supplement
/-- Theorem 8.4, p.25 (PDF26): exact nested floor/ceiling construction,
all allowed r, and no w<k restriction. The hypotheses give q≥1. -/
theorem theorem_8_4 (k n w r : ℕ) (hk : 1 ≤ k) (hn : 1 ≤ n)
(hw : 3 ≤ w) (hr : 1 ≤ r) (hrw : r ≤ (w - 1) / 2) :
let q := (w - 2) / (2 * r - 1)
let b := Nat.ceil ((k : ℝ) / (q : ℝ))
∃ A : MABP (SetMultCost.IMMVar k n), A.output = SetMultCost.imm ℝ k n ∧
A.width ≤ w ∧
A.depth ≤ n * b ^ (r * (Nat.ceil ((n : ℝ) ^ (1 / (r : ℝ))) - 1)) := by sorry
end MonoABPWidth.Hierarchy.Supplement
Source
Julian Dörfler, Alexander Rogovskyy, STOC 2027 submission #927 (October 2026), Theorem 8.4, p.25, PDF26