ECCC-Report TR02-012https://eccc.weizmann.ac.il/report/2002/012Comments and Revisions published for TR02-012en-usTue, 05 Feb 2002 19:06:41 +0200
Paper TR02-012
| On the Complexity of Matrix Product |
Ran Raz
https://eccc.weizmann.ac.il/report/2002/012We 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 the size of each matrix).
That is, our lower bound is super-linear in the number of inputs
and is applied for circuits that use addition gates, product gates
and products with field elements of absolute value up to 1.
More generally, for any $c = c(m) \ge 1$,
we obtain a lower bound of $\Omega(m^2 \log_{2c} 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 $c$.
We also prove size-depth tradeoffs for such circuits.
Tue, 05 Feb 2002 19:06:41 +0200https://eccc.weizmann.ac.il/report/2002/012