Lower Bounds for Matrix Product
Amir Shpilka · SIAM Journal on Computing · 2003
We prove lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two n × n matrices over finite fields. In particular we obtain the following results: We show that the number of product gates in any bilinear (or quadratic) circuit that computes the product of two n × n matrices over ${\rm GF}(2)$ is at least 3n 2 - o(n 2 ). We show that the number of product gates in any bilinear circuit that computes the product of two n × n matrices over ${\rm GF}(q)$ is at least $(2.5 + \frac{1.5}{q^3 -1})n^2 -o(n^2)$. These results improve the former results of [N. H. Bshouty, SIAM J. Comput., 18 (1989), pp. 759-765; M. Bläser, Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1999, pp. 45-50], who proved lower bounds of 2.5 n 2 - o(n 2 ).