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

We study the formula complexity of Iterated Sub-Permutation Matrix Multiplication, the logspacecomplete 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(dk 1/d ) size monotone formulas of two distinct types: (unbounded fan-in) AC 0 formulas of depth d+ 1 and (semi-unbounded fan-in) SAC 0 formulas of -depth d and -fan-in k 1/d . The results of this paper give • matching n Ω(dk 1/d ) lower bounds for monotone AC 0 and SAC 0 formulas for all k ≤ log log n, as well as

• slightly weaker n Ω(dk 1/2d ) lower bounds for non-monotone AC 0 and SAC 0 formulas.

These size-depth tradeoffs converge at d = log k to tight n Ω(log k) lower bounds for both unboundeddepth monotone formulas [21] and bounded-depth non-monotone formulas [23]. Our non-monotone lower bounds extend to the more restricted Iterated Permutation Matrix Multiplication problem, improving the previous n k 1/ exp(O(d)) tradeoff for this problem [4].