Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits
Jan Johannsen (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
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 ≥ 1.