Size-depth trade-offs for monotone arithmetic circuits

Marc Snir

doi:10.1016/0304-3975(91)90173-Y

Size-depth trade-offs for monotone arithmetic circuits

Research output: Contribution to journal › Article › peer-review

Abstract

Consider the problem of computing the product a¹A⁽¹⁾⋯A^(t)b, where A⁽¹⁾,...,A^(t) are n × n matrices, a and b are vectors. We show that the size s and depth d of monotone arithmetic circuits for this problem are related as s + n³d = Ω(tn³) Thus, a reduction to depth d = o(t) requires an increase from (optimal) size n²t to size n³t. A similar trade-off is shown for the evaluation of linear recurrences.

Original language	English (US)
Pages (from-to)	85-93
Number of pages	9
Journal	Theoretical Computer Science
Volume	82
Issue number	1
DOIs	https://doi.org/10.1016/0304-3975(91)90173-Y
State	Published - May 22 1991
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1016/0304-3975(91)90173-Y

Library availability

Discover UIUC Full Text

Cite this

@article{f27845130ca04ed1a5cb25cd33a29fa3,

title = "Size-depth trade-offs for monotone arithmetic circuits",

abstract = "Consider the problem of computing the product a1A(1)⋯A(t)b, where A(1),...,A(t) are n × n matrices, a and b are vectors. We show that the size s and depth d of monotone arithmetic circuits for this problem are related as s + n3d = Ω(tn3) Thus, a reduction to depth d = o(t) requires an increase from (optimal) size n2t to size n3t. A similar trade-off is shown for the evaluation of linear recurrences.",

author = "Marc Snir",

year = "1991",

month = may,

day = "22",

doi = "10.1016/0304-3975(91)90173-Y",

language = "English (US)",

volume = "82",

pages = "85--93",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Size-depth trade-offs for monotone arithmetic circuits

AU - Snir, Marc

PY - 1991/5/22

Y1 - 1991/5/22

N2 - Consider the problem of computing the product a1A(1)⋯A(t)b, where A(1),...,A(t) are n × n matrices, a and b are vectors. We show that the size s and depth d of monotone arithmetic circuits for this problem are related as s + n3d = Ω(tn3) Thus, a reduction to depth d = o(t) requires an increase from (optimal) size n2t to size n3t. A similar trade-off is shown for the evaluation of linear recurrences.

AB - Consider the problem of computing the product a1A(1)⋯A(t)b, where A(1),...,A(t) are n × n matrices, a and b are vectors. We show that the size s and depth d of monotone arithmetic circuits for this problem are related as s + n3d = Ω(tn3) Thus, a reduction to depth d = o(t) requires an increase from (optimal) size n2t to size n3t. A similar trade-off is shown for the evaluation of linear recurrences.

UR - http://www.scopus.com/inward/record.url?scp=0026152558&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026152558&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(91)90173-Y

DO - 10.1016/0304-3975(91)90173-Y

M3 - Article

AN - SCOPUS:0026152558

VL - 82

SP - 85

EP - 93

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1

ER -

Size-depth trade-offs for monotone arithmetic circuits

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this