Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- 1 May 1990
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 3 (2) , 255-265
- https://doi.org/10.1137/0403021
Abstract
No abstract availableThis publication has 8 references indexed in Scilit:
- Short monotone formulae for the majority functionPublished by Elsevier ,2004
- The monotone circuit complexity of boolean functionsCombinatorica, 1987
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983
- Tree-size bounded alternationJournal of Computer and System Sciences, 1980
- On the depth complexity of formulasTheory of Computing Systems, 1979
- Random walks, universal traversal sequences, and the complexity of maze problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Method of determining lower bounds for the complexity of P-schemesMathematical Notes, 1971
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952