Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR01-060 | 23rd August 2001 00:00

#### Lower bounds for matrix product

TR01-060
Authors: Amir Shpilka
Publication: 3rd September 2001 11:46
Keywords:

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
that computes the product of two $n \times n$ matrices over $GF(2)$ is at
least $3 n^2 - o(n^2)$.
that computes the product of two $n \times n$ matrices over $GF(p)$ is at
least $(2.5 + \frac{1.5}{p^3 -1})n^2 -o(n^2)$.
(99) who proved lower bounds of $2.5 n^2 - o(n^2)$.