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

Johannsen, Jan

Geodesic

Parcourir par

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

Johannsen, Jan

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 3, pp. 277-286

Voir la notice de l'article provenant de la source Numdam

Résumé

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

MR Zbl

Classification : 68Q17, 68Q15
Keywords: monotone circuit, semi-unbounded fan-in, communication complexity, lower bound

@article{ITA_2001__35_3_277_0,
     author = {Johannsen, Jan},
     title = {Depth lower bounds for monotone semi-unbounded fan-in circuits},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {277--286},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {3},
     year = {2001},
     mrnumber = {1869218},
     zbl = {1052.68053},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ITA_2001__35_3_277_0/}
}

TY  - JOUR
AU  - Johannsen, Jan
TI  - Depth lower bounds for monotone semi-unbounded fan-in circuits
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
SP  - 277
EP  - 286
VL  - 35
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/item/ITA_2001__35_3_277_0/
LA  - en
ID  - ITA_2001__35_3_277_0
ER  -

%0 Journal Article
%A Johannsen, Jan
%T Depth lower bounds for monotone semi-unbounded fan-in circuits
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 277-286
%V 35
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/ITA_2001__35_3_277_0/
%G en
%F ITA_2001__35_3_277_0

Johannsen, Jan. Depth lower bounds for monotone semi-unbounded fan-in circuits. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 3, pp. 277-286. http://geodesic.mathdoc.fr/item/ITA_2001__35_3_277_0/