Size-depth trade-offs for monotone arithmetic circuits
From MaRDI portal
(Redirected from Publication:804295)
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
Cites work
- scientific article; zbMATH DE number 3557223 (Why is no real title available?)
- Depth-size trade-offs for parallel prefix computation
- Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
- Fast Parallel Computation of Polynomials Using Few Processors
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- The Complexity of Parallel Evaluation of Linear Recurrences
- The Parallel Evaluation of General Arithmetic Expressions
- The complexity of computations by networks
- Time and Parallel Processor Bounds for Linear Recurrence Systems
Cited in
(8)- Monotone circuits for matching require linear depth
- Size-Depth Tradeoffs for Algebraic Formulas
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- A complexity theory of efficient parallel algorithms
- A weight-size trade-off for circuits with MOD \(m\) gates
- Lower bounds for monotone counting circuits
- Lower bounds on the depth of monotone arithmetic computations
- Lower bounds on monotone arithmetic circuits with restricted depths
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)
