Depth lower bounds for monotone semi-unbounded fan-in circuits
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 35 (2001) no. 3, pp. 277-286.

The depth hierarchy results for monotone circuits of Raz and McKenzie [5] are extended to the case of monotone circuits of semi-unbounded fan-in. It follows that the inclusions $N{C}^{i}\subseteq SA{C}^{i}\subseteq A{C}^{i}$ are proper in the monotone setting, for every $i\ge 1$.

Classification: 68Q17,  68Q15
Keywords: monotone circuit, semi-unbounded fan-in, communication complexity, lower bound
@article{ITA_2001__35_3_277_0,
author = {Johannsen, Jan},
title = {Depth lower bounds for monotone semi-unbounded fan-in circuits},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {277--286},
publisher = {EDP-Sciences},
volume = {35},
number = {3},
year = {2001},
zbl = {1052.68053},
mrnumber = {1869218},
language = {en},
url = {http://archive.numdam.org/item/ITA_2001__35_3_277_0/}
}
TY  - JOUR
AU  - Johannsen, Jan
TI  - Depth lower bounds for monotone semi-unbounded fan-in circuits
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
DA  - 2001///
SP  - 277
EP  - 286
VL  - 35
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2001__35_3_277_0/
UR  - https://zbmath.org/?q=an%3A1052.68053
UR  - https://www.ams.org/mathscinet-getitem?mr=1869218
LA  - en
ID  - ITA_2001__35_3_277_0
ER  -
%0 Journal Article
%A Johannsen, Jan
%T Depth lower bounds for monotone semi-unbounded fan-in circuits
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 277-286
%V 35
%N 3
%I EDP-Sciences
%G en
%F ITA_2001__35_3_277_0
Johannsen, Jan. Depth lower bounds for monotone semi-unbounded fan-in circuits. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 35 (2001) no. 3, pp. 277-286. http://archive.numdam.org/item/ITA_2001__35_3_277_0/

[1] A. Borodin, S.A. Cook, P.W. Dymond, W.L. Ruzzo and M. Tompa, Two applications of inductive counting for complementation problems. SIAM J. Comput. 18 (1989) 559-578. | MR | Zbl

[2] M. Grigni and M. Sipser, Monotone complexity, in Boolean Function Complexity, edited by M.S. Paterson. Cambridge University Press (1992) 57-75. | MR | Zbl

[3] M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math. 3 (1990) 255-265. | MR | Zbl

[4] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). | MR | Zbl

[5] R. Raz and P. Mckenzie, Separation of the monotone $NC$ hierarchy. Combinatorica 19 (1999) 403-435. | MR | Zbl

[6] H. Venkateswaran, Properties that characterize LOGCFL. J. Comput. System Sci. 43 (1991) 380-404. | MR | Zbl