Monotone circuits for matching require linear depth
- 1 July 1992
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 39 (3) , 736-744
- https://doi.org/10.1145/146637.146684
Abstract
It is proven that monotone circuits computing the perfect matching function on n -vertex graphs require Ω( n ) depth. This implies an exponential gap between the depth of monotone and nonmonotone circuits.Keywords
This publication has 5 references indexed in Scilit:
- A simple lower bound for monotone clique using a communication gameInformation Processing Letters, 1992
- Monotone Circuits for Connectivity Require Super-Logarithmic DepthSIAM Journal on Discrete Mathematics, 1990
- The gap between monotone and non-monotone circuit complexity is exponentialCombinatorica, 1988
- Monotone versus positiveJournal of the ACM, 1987
- The monotone circuit complexity of boolean functionsCombinatorica, 1987