Size-depth trade-offs for monotone arithmetic circuits
From MaRDI portal
Publication:804295
DOI10.1016/0304-3975(91)90173-YzbMATH Open0727.68049MaRDI QIDQ804295FDOQ804295
Authors: Marc Snir 
Publication date: 1991
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
- Lower bounds on monotone arithmetic circuits with restricted depths
- On the Complexity of Matrix Product
- Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- Lower bounds for monotone counting circuits
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16)
Cites Work
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
- Fast Parallel Computation of Polynomials Using Few Processors
- The Parallel Evaluation of General Arithmetic Expressions
- The complexity of computations by networks
- Depth-size trade-offs for parallel prefix computation
- Time and Parallel Processor Bounds for Linear Recurrence Systems
- The Complexity of Parallel Evaluation of Linear Recurrences
- Title not available (Why is that?)
Cited In (8)
- Monotone circuits for matching require linear depth
- A complexity theory of efficient parallel algorithms
- Lower bounds for monotone counting circuits
- Size-Depth Tradeoffs for Algebraic Formulas
- A weight-size trade-off for circuits with MOD \(m\) gates
- Lower bounds on monotone arithmetic circuits with restricted depths
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- Lower bounds on the depth of monotone arithmetic computations
This page was built for publication: Size-depth trade-offs for monotone arithmetic circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804295)
