Amir Shpilka
<P>
Title: Lower bounds for matrix product.
<P>
Abstract: 
<p>
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:

<P>
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)$.
<P>

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)$.
<P>

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)$.
<P>

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.