Geodesic
Upper bounds on the formula size of symmetric Boolean functions
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 5 (2014), pp. 38-52

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

It is proved that complexity of implementation of the counting function of $n$ Boolean variables with binary formulae is at most $n^{3.03}$ and is at most $n^{4.47}$ with respect to DeMorgan formulae. Hence, the same bounds hold for the formula size of any threshold symmetric function of $n$ variables, particularly, for majority function. The following bounds are proved for the formula size of any symmetric Boolean function of $n$ variables: $n^{3.04}$ with respect to binary formulae and $n^{4.48}$ with respect to DeMorgan formulae. A proof is based on modular arithmetic.
Keywords: formula size, symmetric Boolean functions, majority function
Mots-clés : multiplication. 
@article{IVM_2014_5_a3,
     author = {I. S. Sergeev},
     title = {Upper bounds on the formula size of symmetric {Boolean} functions},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {38--52},
     publisher = {mathdoc},
     number = {5},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2014_5_a3/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - Upper bounds on the formula size of symmetric Boolean functions
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2014
SP  - 38
EP  - 52
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2014_5_a3/
LA  - ru
ID  - IVM_2014_5_a3
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T Upper bounds on the formula size of symmetric Boolean functions
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2014
%P 38-52
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2014_5_a3/
%G ru
%F IVM_2014_5_a3
I. S. Sergeev. Upper bounds on the formula size of symmetric Boolean functions. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 5 (2014), pp. 38-52. http://geodesic.mathdoc.fr/item/IVM_2014_5_a3/