Low-depth arithmetic complexity of the product of $k$ matrices

Question

Is anything known about the size of $\Sigma\Pi\Sigma$ (or other constant depth) circuits for the product of $k$ matrices?

Trivial upper bounds (up to small factors) are:

• if $k=2$, then there are $\Sigma\Pi\Sigma$ circuits of size $n^{\omega}$ (where $\omega$ is the matrix multiplication exponent.)
• if $k>2$, then there are $\Sigma\Pi\Sigma$ circuits of size $n^{k+1}$.
• if $k>2$, then there are $O(log(k))$-depth circuits of size $n^{\omega}$.

Is it possible to construct circuits of size $n^{\omega}$ for every $k$, for some fixed depth? Is it even possible to beat the trivial construction?

Answer 1

I am not sure about specifically depth-three lower bounds, but there has been a lot of depth-4 (and 5) lower bounds, usually assuming other constraints as well. For instance (and without any claim of exhaustivity):

• Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication.
• Suryajith Chillara, Partha Mukhopadhyay. Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach.
• Suman K. Bera, Amit Chakrabarti. A Depth-Five Lower Bound for Iterated Matrix Multiplication.