The Structural Complexity of Matrix-Vector Multiplication

Emile Anand, Jan van den Brand, Rose McCarty

We consider the problem of preprocessing an $n\times n$ matrix $\mathbf{M}$, and supporting queries that, for any vector $v$, returns the matrix-vector product $\mathbf{M}v$. This…