Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits
Institut für Informatik,
80538 München, Germany; e-mail: email@example.com
Accepted: 8 August 2001
The depth hierarchy results for monotone circuits of Raz and McKenzie  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.
Mathematics Subject Classification: 68Q17 / 68Q15
Key words: Monotone circuit / semi-unbounded fan-in / communication complexity / lower bound.
© EDP Sciences, 2001