Size-depth trade-offs for monotone arithmetic circuits
type: Item
instance of: scholarly article
title: Size-depth trade-offs for monotone arithmetic circuits
zbMATH Open document ID: 0727.68049
DOI: 10.1016/0304-3975(91)90173-Y
author: Marc Snir
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
review text: The paper deals with the size-depth trade-off for monotone arithmetic circuits computing the \(product!a^ TA_ 1...A_ t\cdot b\) where \(A_ 1,...,A_ t\) are \(n\times n\) matrics, a and b are vectors. It is proved that if a monotone circuit computes this product in d parallel multiplication steps and with s multiplications, then \(s+2d(n^ 3-n^ 2)\geq (t+2)n^ 3-2n^ 2+n\). This inequality is tight; a matching upper bound can be achieved for any d in the range \(1+\log t\leq d\leq t/2+1\). In this range, any decrease of one in d requires an increase of \(2(n^ 3- n^ 2)\) in s. It seems extremely hard to obtain similar trade-off for general circuits, i.e. for circuits with the subtraction.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 4201624
zbMATH Keywords: lower bounds
zbMATH Keywords: size-depth trade-off
zbMATH Keywords: monotone arithmetic circuits
reviewed by: Stasys Jukna
MaRDI profile type: Publication
cites work: The Parallel Evaluation of General Arithmetic Expressions
cites work: Time and Parallel Processor Bounds for Linear Recurrence Systems
cites work: Q4133124
cites work: The Complexity of Parallel Evaluation of Linear Recurrences
cites work: Some Exact Complexity Results for Straight-Line Computations over Semirings
cites work: Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
cites work: The complexity of computations by networks
cites work: Depth-size trade-offs for parallel prefix computation
cites work: Fast Parallel Computation of Polynomials Using Few Processors
description: scientific article; zbMATH DE number 4201624