Size-depth trade-offs for monotone arithmetic circuits

DOI10.1016/0304-3975(91)90173-YzbMath0727.68049MaRDI QIDQ804295

Marc Snir

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

lower boundsmonotone arithmetic circuitssize-depth trade-off

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16)

Related Items (3)

Lower bounds for monotone counting circuits ⋮ A complexity theory of efficient parallel algorithms ⋮ Lower bounds on the depth of monotone arithmetic computations

Cites Work

• Unnamed Item
• Fast Parallel Computation of Polynomials Using Few Processors
• Depth-size trade-offs for parallel prefix computation
• Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
• The complexity of computations by networks
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Time and Parallel Processor Bounds for Linear Recurrence Systems
• The Complexity of Parallel Evaluation of Linear Recurrences
• The Parallel Evaluation of General Arithmetic Expressions

This page was built for publication: Size-depth trade-offs for monotone arithmetic circuits