Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-27T07:28:43.087Z Has data issue: false hasContentIssue false
  • English
  • Français

Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits

Published online by Cambridge University Press:  15 April 2002

Jan Johannsen
Jan Johannsen*
Affiliation:
Institut für Informatik, Ludwig-Maximilians-Universität München, Oettingenstraße 67, 80538 München, Germany; e-mail: [email protected]
Get access

Abstract

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 NCi ⊆ SACi ⊆ ACi are proper in the monotone setting, for every i ≥ 1.

Keywords

Monotone circuitsemi-unbounded fan-incommunication complexitylower bound.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 35 , Issue 3 , May 2001 , pp. 277 - 286
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Borodin, A., Cook, S.A., Dymond, P.W., Ruzzo, W.L. and Tompa, M., Two applications of inductive counting for complementation problems. SIAM J. Comput. 18 (1989) 559-578. CrossRef
M. Grigni and M. Sipser, Monotone complexity, in Boolean Function Complexity, edited by M.S. Paterson. Cambridge University Press (1992) 57-75.
Karchmer, M. and Wigderson, A., Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math. 3 (1990) 255-265. CrossRef
E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997).
Raz, R. and McKenzie, P., Separation of the monotone NC hierarchy. Combinatorica 19 (1999) 403-435. CrossRef
Venkateswaran, H., Properties that characterize LOGCFL. J. Comput. System Sci. 43 (1991) 380-404. CrossRef