Geodesic
Lower estimates of circuit complexity in the basis of antichain functions
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2013), pp. 17-23

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

The antichain function is a characteristic function of an antichain in the Boolean cube. The set of antichain functions is an infinite complete basis. We study the computational complexity of Boolean functions over an antichain functional basis. In this paper we prove an asymptotic lower bound of order $\sqrt{n}$ on the computational complexity of the linear function, the majority function, and almost all Boolean functions of $n$ variables. 
@article{VMUMM_2013_2_a3,
     author = {O. V. Podolskaya},
     title = {Lower estimates of circuit complexity in the basis of antichain functions},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {17--23},
     publisher = {mathdoc},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2013_2_a3/}
}
TY  - JOUR
AU  - O. V. Podolskaya
TI  - Lower estimates of circuit complexity in the basis of antichain functions
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2013
SP  - 17
EP  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2013_2_a3/
LA  - ru
ID  - VMUMM_2013_2_a3
ER  - 
%0 Journal Article
%A O. V. Podolskaya
%T Lower estimates of circuit complexity in the basis of antichain functions
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2013
%P 17-23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMUMM_2013_2_a3/
%G ru
%F VMUMM_2013_2_a3
O. V. Podolskaya. Lower estimates of circuit complexity in the basis of antichain functions. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2013), pp. 17-23. http://geodesic.mathdoc.fr/item/VMUMM_2013_2_a3/