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.
Original language | English (US) |
---|---|
Pages (from-to) | 85-93 |
Number of pages | 9 |
Journal | Theoretical Computer Science |
Volume | 82 |
Issue number | 1 |
DOIs | |
State | Published - May 22 1991 |
Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science