Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
share
In this paper, we study the algebraic formula complexity of multiplying d many 2× 2 matrices, denoted IMM_d, and show that the well-known divide-and-conquer algorithm cannot be significantly improved at any depth, as long as the formulas are multilinear. Formally, for each depth Δ≤ d, we show that any product-depth Δ multilinear formula for IMM_d must have size (Ω(Δ d^1/Δ)). It also follows from this that any multilinear circuit of product-depth Δ for the same polynomial of the above form must have a size of (Ω(d^1/Δ)). In particular, any polynomial-sized multilinear formula for IMM_d must have depth Ω( d), and any polynomial-sized multilinear circuit for IMM_d must have depth Ω( d/ d). Both these bounds are tight up to constant factors. 1. Depth-reduction: A well-known result of Brent (JACM 1974) implies that any formula of size s can be converted to one of size s^O(1) and depth O( s); further, this reduction continues to hold for multilinear formulas. Our lower bound implies that any depth-reduction in the multilinear setting cannot reduce the depth to o( s) without a superpolynomial blow-up in size. 2. Separations from general formulas: Our result, along with a non-trivial upper bound for IMM_d implied by a result of Gupta, Kamath, Kayal and Saptharishi (SICOMP 2016), shows that for any size s and product-depth Δ = o( s), general formulas of size s and product-depth Δ cannot be converted to multilinear formulas of size s^ω(1) and product-depth Δ, when the underlying field has characteristic zero.
READ FULL TEXT