A Depth-Five Lower Bound for Iterated Matrix Multiplication

Abstract

We prove that certain instances of the iterated matrix multiplication (IMM) family of polynomials with $N$ variables and degree $n$ require $N^{\Omega(\sqrt n)}$ gates when expressed as a homogeneous depth-five $\Sigma \Pi \Sigma \Pi \Sigma$ arithmetic circuit with the bottom fan-in bounded by $N^{{1}/{2}-\varepsilon}$. By a depth-reduction result of Tavenas, this size lower bound is optimal and can be achieved by the weaker class of homogeneous depth-four $\Sigma\Pi\Sigma\Pi$ circuits.

Our result extends a recent result of Kumar and Saraf, who gave the same $N^{\Omega(\sqrt n)}$ lower bound for homogeneous depth-four $\Sigma \Pi \Sigma \Pi$ circuits computing IMM. It is analogous to a recent result of Kayal and Saha, who gave the same lower bound for homogeneous $\Sigma \Pi \Sigma \Pi \Sigma$ circuits (over characteristic zero) with bottom fan-in at most $N^{1-\varepsilon}$, for the harder problem of computing certain polynomials defined by Nisan–Wigderson designs.

Publication
Conference on Computational Complexity (CCC 2015)