Size-depth trade-offs for monotone arithmetic circuits

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)85-93
Number of pages9
JournalTheoretical Computer Science
Volume82
Issue number1
DOIs
StatePublished - May 22 1991
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Size-depth trade-offs for monotone arithmetic circuits'. Together they form a unique fingerprint.

Cite this