Geodesic
Circuit complexity of symmetric Boolean functions in antichain basis
Diskretnaya Matematika, Tome 27 (2015) no. 3, pp. 95-107.

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

We study the circuit complexity of Boolean functions in an infinite basis consisting of all characteristic functions of antichains over the Boolean cube. For an arbitrary symmetric function we obtain the exact value of its circuit complexity in this basis. In particular, we prove that the circuit complexities of the parity function and the majority function of $n$ variables for all integers $n\geqslant1$ in this basis are $\lfloor \frac{n+1}{2} \rfloor$ and $\left\lfloor \frac{n}{2} \right \rfloor +1$ respectively. For the maximum circuit complexity of $n$-variable Boolean functions in this basis, we show that its order of growth is equal to $n.$ \hspace{12cm} \linebreak The research is supported by the Russian Foundation for Basic Research, project 14–01–00598.
Keywords: Boolean circuit complexity, antichain functions, Boolean circuits, symmetric Boolean functions, the Shannon function. 
@article{DM_2015_27_3_a6,
     author = {Olga V. Podolskaya},
     title = {Circuit complexity of symmetric {Boolean} functions in antichain basis},
     journal = {Diskretnaya Matematika},
     pages = {95--107},
     publisher = {mathdoc},
     volume = {27},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2015_27_3_a6/}
}
TY  - JOUR
AU  - Olga V. Podolskaya
TI  - Circuit complexity of symmetric Boolean functions in antichain basis
JO  - Diskretnaya Matematika
PY  - 2015
SP  - 95
EP  - 107
VL  - 27
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2015_27_3_a6/
LA  - ru
ID  - DM_2015_27_3_a6
ER  - 
%0 Journal Article
%A Olga V. Podolskaya
%T Circuit complexity of symmetric Boolean functions in antichain basis
%J Diskretnaya Matematika
%D 2015
%P 95-107
%V 27
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2015_27_3_a6/
%G ru
%F DM_2015_27_3_a6
Olga V. Podolskaya. Circuit complexity of symmetric Boolean functions in antichain basis. Diskretnaya Matematika, Tome 27 (2015) no. 3, pp. 95-107. http://geodesic.mathdoc.fr/item/DM_2015_27_3_a6/

[1] Kasim-Zade O. M., “O slozhnosti skhem v odnom beskonechnom bazise”, Vestnik Moskovskogo Universiteta. Ser. 1. Matem. Mekh., 1994, no. 6, 40–44 | MR | Zbl

[2] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Moskovskogo un-ta, Moskva, 1984, 138 pp.

[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”, Vestnik Moskovskogo Universiteta. Ser. 1. Matem. Mekh., 2013, no. 2, 17–23 | MR | Zbl

[5] Podolskaya O. V., “Ob otsenkakh slozhnosti skhem v odnom beskonechnom bazise”, Materialy IX Molodezhnoi nauchnoi shkoly po diskretnoi matematike i ee prilozheniyam (Moskva, 16–23 sentyabrya 2013), 2013, 97–100

[6] Lupanov O. B., “Ob odnom metode sinteza skhem”, Izvestiya vysshikh uchebnykh zavedenii. Radiofizika, 1:1 (1958), 120–140