A direct version of Shamir and Snir's lower bounds on monotone circuit depth

DOI10.1016/0020-0190(94)90061-2zbMath0795.68102OpenAlexW2080529336MaRDI QIDQ1318755

Prasoon Tiwari, Martin Tompa

Publication date: 5 April 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90061-2

zbMATH Keywords

parallel algorithmsarithmetic circuitsformula depth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Distributed algorithms (68W15)

Related Items (8)

Lower bounds for monotone counting circuits ⋮ Formulas versus Circuits for Small Distance Connectivity ⋮ Lower bounds on arithmetic circuits via partial derivatives ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Non-commutative circuits and the sum-of-squares problem ⋮ Regular expression length via arithmetic formula complexity ⋮ Tropical Complexity, Sidon Sets, and Dynamic Programming

Cites Work

• Negation can be exponentially powerful
• On the depth complexity of formulas

This page was built for publication: A direct version of Shamir and Snir's lower bounds on monotone circuit depth