On the complexity of matrix product

Research output: Contribution to journalConference articlepeer-review

26 Scopus citations

Abstract

We prove a lower bound of Ω(m2 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 × 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) ≥ 1, we obtain a lower bound of Ω(m2log2c 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.

Original languageAmerican English
Pages (from-to)144-151
Number of pages8
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 2002
Externally publishedYes
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'On the complexity of matrix product'. Together they form a unique fingerprint.

Cite this