Geodesic
Complexity of linear and majority functions in the basis of antichain functions
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2016), pp. 51-52 
O. V. Podolskaya. Complexity of linear and majority functions in the basis of antichain functions. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2016), pp. 51-52. http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a9/
@article{VMUMM_2016_2_a9,
     author = {O. V. Podolskaya},
     title = {Complexity of linear and majority functions in the basis of antichain functions},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {51--52},
     year = {2016},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a9/}
}
TY  - JOUR
AU  - O. V. Podolskaya
TI  - Complexity of linear and majority functions in the basis of antichain functions
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2016
SP  - 51
EP  - 52
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a9/
LA  - ru
ID  - VMUMM_2016_2_a9
ER  - 
%0 Journal Article
%A O. V. Podolskaya
%T Complexity of linear and majority functions in the basis of antichain functions
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2016
%P 51-52
%N 2
%U http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a9/
%G ru
%F VMUMM_2016_2_a9

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

The complexity circuits of Boolean functions is studied in a basis consisting of all characteristic functions of antichains over the Boolean cube. It is established that the circuit complexity of an $n$-variable parity function is $\left\lfloor \frac{n+1}{2}\right\rfloor$ and the complexity of its negation equals the complexity of the $n$-variable majority function which is $\left\lceil \frac{n+1}{2} \right\rceil$.

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

[2] Lupanov O.B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, M., 1984

[3] 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 | Zbl

[4] Podolskaya O.V., “O nizhnikh otsenkakh slozhnosti skhem v bazise antitsepnykh funktsii”, Vestn. Mosk. un-ta. Matem. Mekhan., 2013, no. 2, 17–23 | MR | Zbl

[5] Podolskaya O.V., “Ob otsenkakh slozhnosti skhem v odnom beskonechnom bazise”, Mat-ly IX Molodezhnoi nauchnoi shkoly po diskretnoi matematike i ee prilozheniyam (Moskva, 16–23 sentyabrya 2013 g.), IPM im. M. V. Keldysha RAN, M., 2013, 97–100