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 ≤ log k , this problem is solvable by size n O ( dk 1/ d ) monotone AC 0 formulas of depth d +1, as well as semi-unbounded fan-in “ SAC 0 ” formulas of ∧-depth d and ∧-fan-in O ( k 1/ d ). In this paper, we prove matching n Ω( dk 1/ d ) lower bounds for monotone AC 0 and SAC 0 formulas for all k ≤ loglog n , and slightly weaker n Ω( dk 1/2 d ) lower bounds for non-monotone AC 0 and SAC 0 formulas. These size-depth tradeoffs converge at d = log k to known asymptotically tight n Ω(log k ) 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 n k exp(− O ( d )) tradeoff.

Authors

• Benjamin Rossman

Keywords

• circuit complexity
• size-depth tradeoffs