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

We study the formula complexity of Iterated Sub-Permutation Matrix Multiplication, the logspace-complete 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 ≤ log k, this problem is solvable by n^O(dk1/d) size monotone formulas of two distinct types: (unbounded fan-in) AC⁰ formulas of depth $d+1$ and (semi-unbounded fan-in) SAC⁰ formulas of -depth d and -fan-in k1/d. The results of this paper give matching n^Ω(dk1/d) lower bounds for monotone AC⁰ and SAC⁰ formulas for all k ≤ loglog n, as well as slightly weaker n^Ω(dk1/2d) lower bounds for non-monotone AC⁰ and SAC⁰ formulas. These size-depth tradeoffs converge at d = log k to tight nΩ(log k) lower bounds for both unbounded-depth monotone formulas [Ros15] and bounded-depth non-monotone formulas [Ros18]. Our non-monotone lower bounds extend to the more restricted Iterated Permutation Matrix Multiplication problem, improving the previous n^k1/exp(O(d)) tradeoff for this problem [BIP98].