Amir Shpilka

Title: Lower bounds for matrix product.

Abstract:

We prove lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two $n \times n$ matrices over finite fields. In particular we obtain the following results:

1. We show that the number of product gates in any bilinear (or quadratic) circuit that computes the product of two $n \times n$ matrices over $GF(2)$ is at least $3 n^2 - o(n^2)$.

2. We show that the number of product gates in any bilinear circuit that computes the product of two $n \times n$ matrices over $GF(p)$ is at least ${2.5 + (1.5)/(p^3 -1)}n^2 -o(n^2)$.

These results improve the former results of Bshouty ('89) and Bl\"{a}ser ('99), who proved lower bounds of $2.5 n^2 - o(n^2)$.

Our techniques includes a reduction from circuits that compute the product of two $n \times n$ matrices to a special kind of linear codes - linear codes of matrices. We then show that the problem of proving lower bounds on the number of product gates in the circuit translates to a problem on these codes.