On the complexity of matrix product

Ran Raz

doi:10.1145/509907.509932

On the complexity of matrix product

Ran Raz

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

48 Scopus citations

Abstract

We prove a lower bound of Ω(m² 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 Ω(m²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.

Original language	English (US)
Title of host publication	Proceedings of the 34th Annual ACM Symposium on Theory of Computing
Publisher	Association for Computing Machinery (ACM)
Pages	144-151
Number of pages	8
ISBN (Print)	9781581134957
DOIs	https://doi.org/10.1145/509907.509932
State	Published - 2002
Externally published	Yes
Event	34th Annual ACM Symposium on Theory of Computing, STOC 2002 - Montreal, Que., Canada Duration: May 19 2002 → May 21 2002

Publication series

Name	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0734-9025

Conference

Conference	34th Annual ACM Symposium on Theory of Computing, STOC 2002
Country/Territory	Canada
City	Montreal, Que.
Period	5/19/02 → 5/21/02

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/509907.509932

Cite this

@inproceedings{b141b60900884fbbbbaa310993d1e698,

title = "On the complexity of matrix product",

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 {\texttimes} 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.",

author = "Ran Raz",

year = "2002",

doi = "10.1145/509907.509932",

language = "English (US)",

isbn = "9781581134957",

series = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery (ACM)",

pages = "144--151",

booktitle = "Proceedings of the 34th Annual ACM Symposium on Theory of Computing",

address = "United States",

note = "34th Annual ACM Symposium on Theory of Computing, STOC 2002 ; Conference date: 19-05-2002 Through 21-05-2002",

}

Raz, R 2002, On the complexity of matrix product. in Proceedings of the 34th Annual ACM Symposium on Theory of Computing. Conference Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery (ACM), pp. 144-151, 34th Annual ACM Symposium on Theory of Computing, STOC 2002, Montreal, Que., Canada, 5/19/02. https://doi.org/10.1145/509907.509932

TY - GEN

T1 - On the complexity of matrix product

AU - Raz, Ran

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0036036841

UR - https://www.scopus.com/pages/publications/0036036841#tab=citedBy

U2 - 10.1145/509907.509932

DO - 10.1145/509907.509932

M3 - Conference contribution

AN - SCOPUS:0036036841

SN - 9781581134957

T3 - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 144

EP - 151

BT - Proceedings of the 34th Annual ACM Symposium on Theory of Computing

PB - Association for Computing Machinery (ACM)

T2 - 34th Annual ACM Symposium on Theory of Computing, STOC 2002

Y2 - 19 May 2002 through 21 May 2002

ER -

On the complexity of matrix product

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this