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

Jan Johannsen

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

  • Volume: 35, Issue: 3, page 277-286
  • ISSN: 0988-3754

Abstract

top
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 ⊆ S A C i ⊆ A C i are proper in the monotone setting, for every i ≥ 1 .

How to cite

top

Johannsen, Jan. "Depth lower bounds for monotone semi-unbounded fan-in circuits." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.3 (2001): 277-286. <http://eudml.org/doc/92666>.

@article{Johannsen2001,
abstract = {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 $NC^i \subseteq SAC^i \subseteq AC^i$ are proper in the monotone setting, for every $i\ge 1$.},
author = {Johannsen, Jan},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {monotone circuit; semi-unbounded fan-in; communication complexity; lower bound; Boolean functions},
language = {eng},
number = {3},
pages = {277-286},
publisher = {EDP-Sciences},
title = {Depth lower bounds for monotone semi-unbounded fan-in circuits},
url = {http://eudml.org/doc/92666},
volume = {35},
year = {2001},
}

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
PB - EDP-Sciences
VL - 35
IS - 3
SP - 277
EP - 286
AB - 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 $NC^i \subseteq SAC^i \subseteq AC^i$ are proper in the monotone setting, for every $i\ge 1$.
LA - eng
KW - monotone circuit; semi-unbounded fan-in; communication complexity; lower bound; Boolean functions
UR - http://eudml.org/doc/92666
ER -

References

top
  1. [1] A. Borodin, S.A. Cook, P.W. Dymond, W.L. Ruzzo and M. Tompa, Two applications of inductive counting for complementation problems. SIAM J. Comput. 18 (1989) 559-578. Zbl0678.68031MR996836
  2. [2] M. Grigni and M. Sipser, Monotone complexity, in Boolean Function Complexity, edited by M.S. Paterson. Cambridge University Press (1992) 57-75. Zbl0766.68040MR1211867
  3. [3] M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math. 3 (1990) 255-265. Zbl0695.94021MR1039296
  4. [4] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). Zbl0869.68048MR1426129
  5. [5] R. Raz and P. McKenzie, Separation of the monotone N C hierarchy. Combinatorica 19 (1999) 403-435. Zbl0977.68037MR1723255
  6. [6] H. Venkateswaran, Properties that characterize LOGCFL. J. Comput. System Sci. 43 (1991) 380-404. Zbl0776.68046MR1130778

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.