Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication

Iterated Sub-Permutation Matrix Multiplication is the problem of computing the product of k n-by-n Boolean matrices with at most a single 1 in each row and column. For all d ≤ logk, this problem is solvable by size nO(dk1/d) monotone AC0 formulas of depth d+1, as well as semi-unbounded fan-in “SAC0” formulas of ∧-depth d and ∧-fan-in O(k1/d). In this paper, we prove matching nΩ(dk1/d) lower bounds for monotone AC0 and SAC0 formulas for all k ≤ loglogn, and slightly weaker nΩ(dk1/2d) lower bounds for non-monotone AC0 and SAC0 formulas. These size-depth tradeoffs converge at d = logk to known asymptotically tight nΩ(logk) lower bounds for both unbounded-depth monotone formulas and bounded-depth non-monotone formulas. Our lower bounds for non-monotone formulas extend to the Iterated Permutation Matrix Multiplication problem, improving the previous best known nkexp(−O(d)) tradeoff.