So I'm wondering, first off, where I can read up to get a feel for state-of-the-art matrix multiplication concepts. I'll try to be more specific:

I'm wondering if there has been research on circuits that compute a pre-defined matrix function. For instance, if we have a function such as $(AB)+C+(DEF)(AB)$, where all the variables are matrices with given sizes, how efficient can we make a circuit that computes this function? I've been toying with an idea in which the entries are all computed modulo $p$. So I'm wondering, broadly, what I can read up on to be up-to-date.


1 Answer 1


While I don't know about the complexity of matrix polynomials in general, the state of the art in the complexity of matrix multiplication is nicely summarized in a recent ToC Graduate Survey by Markus Bläser.

Computing entries mod $p$ is basically the same as the question of the complexity of performing the computation over the field $\mathbb{F}_p$, which is fairly well-studied (though perhaps not as well-studied as characteristic zero).

Most matrix multiplication research works in the nonuniform setting anyways, so it should almost all be relevant to the question of circuit size.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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