Lower bounds on the depth of monotone arithmetic computations

DOI10.1006/jcom.1998.0494zbMath0936.68045OpenAlexW2127386151MaRDI QIDQ1288530

Don Coppersmith, Baruch Schieber

Publication date: 11 May 1999

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.1998.0494

zbMATH Keywords

monotone arithmetic computations

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cites Work

• Unnamed Item
• Size-depth trade-offs for monotone arithmetic circuits
• On the depth complexity of formulas
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Time Bounds on the Parallel Evaluation of Arithmetic Expressions
• Efficient Parallel Evaluation of Boolean Expressions
• Restructuring of Arithmetic Expressions For Parallel Evaluation
• Computer Search for Numerical Instability
• Reduction of Depth of Boolean Networks with a Fan-In Constraint
• The Parallel Evaluation of General Arithmetic Expressions
• The Parallel Evaluation of Arithmetic Expressions Without Division

This page was built for publication: Lower bounds on the depth of monotone arithmetic computations