Depth lower bounds for monotone semi-unbounded fan-in circuits

Johannsen, Jan

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 3, pp. 277-286.

Résumé

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 S A C^{i} \subseteq A C^{i}$ are proper in the monotone setting, for every $i \geq 1$ .

MR 1869218 | Zbl 1052.68053

Classification : 68Q17, 68Q15
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},
     zbl = {1052.68053},
     mrnumber = {1869218},
     language = {en},
     url = {http://www.numdam.org/item/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://www.numdam.org/item/ITA_2001__35_3_277_0/

Bibliographie

[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 996836 | Zbl 0678.68031

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

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

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

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

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