Lower bounds for depth 4 formulas computing iterated matrix multiplication

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth 4 arithmetic formula computing the product of d generic matrices of size n × n , IMM n,d , has size n Ω(√ d ) as long as d = n O (1) . This improves the result of Nisan and Wigderson (Computational Complexity, 1997) for depth 4 set-multilinear formulas. We also study ΣΠ [ O ( d / t )] ΣΠ [ t ] formulas, which are depth 4 formulas with the stated bounds on the fan-ins of the Π gates. A recent depth reduction result of Tavenas (MFCS, 2013) shows that any n -variate degree d = n O (1) polynomial computable by a circuit of size poly( n ) can also be computed by a depth 4 ΣΠ [ O ( d / t )] ΣΠ [ t ] formula of top fan-in n O ( d / t ) . We show that any such formula computing IMM n,d has top fan-in n Ω( d / t ) , proving the optimality of Tavenas' result. This also strengthens a result of Kayal, Saha, and Saptharishi (ECCC, 2013) which gives a similar lower bound for an explicit polynomial in VNP.

Authors

• Hervé Fournier
• Nutan Limaye
• Guillaume Malod
• Srikanth Srinivasan 0001

Keywords

• arithmetic circuits
• lower bounds
• shifted partial derivatives