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 are proper in the monotone setting, for every .
Mots-clés : 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}, mrnumber = {1869218}, zbl = {1052.68053}, 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 SP - 277 EP - 286 VL - 35 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/item/ITA_2001__35_3_277_0/ 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 %U http://archive.numdam.org/item/ITA_2001__35_3_277_0/ %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, Tome 35 (2001) no. 3, pp. 277-286. http://archive.numdam.org/item/ITA_2001__35_3_277_0/
[1] Two applications of inductive counting for complementation problems. SIAM J. Comput. 18 (1989) 559-578. | MR | Zbl
, , , and ,[2] Monotone complexity, in Boolean Function Complexity, edited by M.S. Paterson. Cambridge University Press (1992) 57-75. | MR | Zbl
and ,[3] Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math. 3 (1990) 255-265. | MR | Zbl
and ,[4] Communication Complexity. Cambridge University Press (1997). | MR | Zbl
and ,[5] Separation of the monotone hierarchy. Combinatorica 19 (1999) 403-435. | MR | Zbl
and ,[6] Properties that characterize LOGCFL. J. Comput. System Sci. 43 (1991) 380-404. | MR | Zbl
,