Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BILINEAR CIRCUITS:
Reports tagged with bilinear circuits:
TR01-060 | 23rd August 2001
Amir Shpilka

#### Lower bounds for matrix product

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) ... more >>>

ISSN 1433-8092 | Imprint