On the complexity of matrix product

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

Our main result is 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 does not 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 superlinear 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. We also prove size-depth tradeoffs for such circuits: We show that if a circuit, as above, is of depth d, then its size is Ω(m2+1/O(d)).

Original languageEnglish (US)
Pages (from-to)1356-1369
Number of pages14
JournalSIAM Journal on Computing
Volume32
Issue number5
DOIs
StatePublished - Aug 1 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Algebraic complexity
  • Arithmetic circuits
  • Bounded coefficients model
  • Circuit complexity
  • Lower bounds
  • Singular values

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

Cite this