Advanced Search

Match of the following rules

Add Sub-clause

Add Another Rule

Contains the following math formula (red border means the formula is incomplete)

Formula preview

Currently displaying 1 – 2 of 2

Order by Relevance | Title | Year of publication

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

Jan Johannsen — 2001

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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$ .

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

Jan Johannsen — 2010

RAIRO - Theoretical Informatics and Applications

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.

Page 1

Download Results (CSV)