Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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