Geodesic
Lower estimates of circuit complexity in the basis of antichain functions
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2013), pp. 17-23 
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/
@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},
     year = {2013},
     number = {2},
     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
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
%U http://geodesic.mathdoc.fr/item/VMUMM_2013_2_a3/
%G ru
%F VMUMM_2013_2_a3

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.

[1] Diskretnaya matematika i matematicheskie voprosy kibernetiki, v. 1, eds. S. V. Yablonskii, O. B. Lupanov, Nauka, M., 1974 | MR

[2] Kasim-Zade O.M., “O slozhnosti realizatsii bulevykh funktsii skhemami v odnom beskonechnom bazise”, Diskretnyi analiz i issledovanie operatsii, 2:1 (1995), 7–20 | MR

[3] Kasim-Zade O.M., “O slozhnosti skhem v odnom beskonechnom bazise”, Vestn. Mosk. un-ta. Matem. Mekhan., 1994, no. 6, 40–44 | MR

[4] Aigner M., Kombinatornaya teoriya, Mir, M., 1982 | MR

[5] Tao T., Vu V., Additive Combinatorics, Cambridge Studies in Advanced Mathematics, 105, Cambridge Univ. Press, Cambridge, 2006 | MR