Geodesic
Bounds for the average-case complexity of monotone Boolean functions
Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 146-153

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider average-case complexity of computing monotone Boolean functions by straight-line programs with a conditional stop over the basis of all Boolean functions of at most two variables. For the set of all $n$-ary monotone Boolean functions new Shannon-type upper and lower bounds for the average-case complexity as $n\to\infty$ are established.
Keywords: monotone Boolean functions, average-case complexity. 
@article{DM_2016_28_2_a13,
     author = {A. V. Chashkin},
     title = {Bounds for the average-case complexity of monotone {Boolean} functions},
     journal = {Diskretnaya Matematika},
     pages = {146--153},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_2_a13/}
}
TY  - JOUR
AU  - A. V. Chashkin
TI  - Bounds for the average-case complexity of monotone Boolean functions
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 146
EP  - 153
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_2_a13/
LA  - ru
ID  - DM_2016_28_2_a13
ER  - 
%0 Journal Article
%A A. V. Chashkin
%T Bounds for the average-case complexity of monotone Boolean functions
%J Diskretnaya Matematika
%D 2016
%P 146-153
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_2_a13/
%G ru
%F DM_2016_28_2_a13
A. V. Chashkin. Bounds for the average-case complexity of monotone Boolean functions. Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 146-153. http://geodesic.mathdoc.fr/item/DM_2016_28_2_a13/