A direct version of Shamir and Snir's lower bounds on monotone circuit depth
From MaRDI portal
Publication:1318755
DOI10.1016/0020-0190(94)90061-2zbMath0795.68102OpenAlexW2080529336MaRDI QIDQ1318755
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
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
This page was built for publication: A direct version of Shamir and Snir's lower bounds on monotone circuit depth
