Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 35, Issue: 3, page 277-286
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topJohannsen, Jan. "Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits." RAIRO - Theoretical Informatics and Applications 35.3 (2010): 277-286. <http://eudml.org/doc/221955>.
@article{Johannsen2010,
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 NCi ⊆ SACi
⊆ ACi are proper in the monotone setting, for every i ≥ 1.
},
author = {Johannsen, Jan},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Monotone circuit; semi-unbounded fan-in; communication complexity;
lower bound.; Boolean functions},
language = {eng},
month = {3},
number = {3},
pages = {277-286},
publisher = {EDP Sciences},
title = {Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits},
url = {http://eudml.org/doc/221955},
volume = {35},
year = {2010},
}
TY - JOUR
AU - Johannsen, Jan
TI - Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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 NCi ⊆ SACi
⊆ ACi are proper in the monotone setting, for every i ≥ 1.
LA - eng
KW - Monotone circuit; semi-unbounded fan-in; communication complexity;
lower bound.; Boolean functions
UR - http://eudml.org/doc/221955
ER -
References
top- 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.
- M. Grigni and M. Sipser, Monotone complexity, in Boolean Function Complexity, edited by M.S. Paterson. Cambridge University Press (1992) 57-75.
- M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math.3 (1990) 255-265.
- E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997).
- R. Raz and P. McKenzie, Separation of the monotone NC hierarchy. Combinatorica19 (1999) 403-435.
- H. Venkateswaran, Properties that characterize LOGCFL. J. Comput. System Sci.43 (1991) 380-404.
NotesEmbed ?
topYou 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.