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?


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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.