<p>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):</p>

<ul>
<li>Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. <a href="http://www.cse.iitb.ac.in/~nutan/papers/imm-merged.pdf">Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication</a>. </li>
<li>Suryajith Chillara, Partha Mukhopadhyay. <a href="http://arxiv.org/abs/1308.1640">Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach</a>.</li>
<li>Suman K. Bera, Amit Chakrabarti. <a href="http://drops.dagstuhl.de/opus/volltexte/2015/5062/">A Depth-Five Lower Bound for Iterated Matrix Multiplication</a>.</li>
</ul>

CC BY-SA 3.0
2016-04-12T12:38:22.570Z
2016-04-12T12:38:22.570Z
Bruno
<p>Is anything known about the size of $\Sigma\Pi\Sigma$ (or other constant depth) circuits for the product of $k$ matrices?</p>

<p>Trivial upper bounds (up to small factors) are:</p>

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

<p>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?</p>

<matrices><arithmetic-circuits><matrix-product><bounded-depth>
Low-depth arithmetic complexity of the product of $k$ matrices
ivmihajlin
# Low-depth arithmetic complexity of the product of $k$ matrices

(Asked by: username_0 on 2016-04-12)

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?

**Tags:** matrices, arithmetic-circuits, matrix-product, bounded-depth

---

## 1 answers

### Answer by username_1 on 2016-04-12. Score: 4 | Accepted answer

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](http://www.cse.iitb.ac.in/~nutan/papers/imm-merged.pdf).
* Suryajith Chillara, Partha Mukhopadhyay. [Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach](http://arxiv.org/abs/1308.1640).
* Suman K. Bera, Amit Chakrabarti. [A Depth-Five Lower Bound for Iterated Matrix Multiplication](http://drops.dagstuhl.de/opus/volltexte/2015/5062/).


---

