spacer
EDP Sciences Journals List
Home arrow Document
Subscriber Authentication Point
   
Issue Theoret. Informatics Appl.
Volume 35, Number 3, May-June 2001
Page(s) 277 - 286
DOI 10.1051/ita:2001120

DOI: 10.1051/ita:2001120


Theoret. Informatics Appl. 35, 277-286 (2001)

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

Jan Johannsen

Institut für Informatik, Ludwig-Maximilians-Universität München, Oettingenstraße 67, 80538 München, Germany;
    e-mail: jjohanns@informatik.uni-muenchen.de

(Received January, 2001. Accepted August 8, 2001)

Abstract
The depth hierarchy results for monotone circuits of Raz and McKenzie (1999) are extended to the case of monotone circuits of semi-unbounded fan-in. It follows that the inclusions $NC^i \subseteq SAC^i \subseteq AC^i$ are proper in the monotone setting, for every $i\geq 1$.


AMS Subject: 68Q17, 68Q15

Key words: Monotone circuit -- semi-unbounded fan-in -- communication complexity -- lower bound.


© EDP Sciences 2001


What is OpenURL?