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"Λ-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.
