ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > RIGIDITY:
Reports tagged with rigidity:
TR02-012 | 3rd February 2002
Ran Raz

On the Complexity of Matrix Product

We prove a lower bound of $\Omega(m^2 \log m)$ for the size of
any arithmetic circuit for the product of two matrices,
over the real or complex numbers, as long as the circuit doesn't
use products with field elements of absolute value larger than 1
(where $m \times m$ is ... more >>>




ISSN 1433-8092 | Imprint