Geodesic
Complexity and depth of formulas for symmetric Boolean functions
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2016), pp. 53-57 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A new approach for implementation of the counting function for a Boolean set is proposed. The approach is based on approximate calculation of sums. Using this approach, new upper bounds for the size and depth of symmetric functions over the basis $B_2$ of all dyadic functions and over the standard basis $B_0 =\{ \wedge, \vee,\overline{\phantom a} \}$ were non-constructively obtained. In particular, the depth of multiplication of $n-$bit binary numbers is asymptotically estimated from above by $4.02\log_2n$ relative to the basis $B_2$ and by $5.14\log_2n$ relative to the basis $B_0$. 
@article{VMUMM_2016_3_a10,
     author = {I. S. Sergeev},
     title = {Complexity and depth of formulas for symmetric {Boolean} functions},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {53--57},
     year = {2016},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2016_3_a10/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - Complexity and depth of formulas for symmetric Boolean functions
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2016
SP  - 53
EP  - 57
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2016_3_a10/
LA  - ru
ID  - VMUMM_2016_3_a10
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T Complexity and depth of formulas for symmetric Boolean functions
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2016
%P 53-57
%N 3
%U http://geodesic.mathdoc.fr/item/VMUMM_2016_3_a10/
%G ru
%F VMUMM_2016_3_a10
I. S. Sergeev. Complexity and depth of formulas for symmetric Boolean functions. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2016), pp. 53-57. http://geodesic.mathdoc.fr/item/VMUMM_2016_3_a10/

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

[2] Khrapchenko V.M., “O slozhnosti realizatsii simmetricheskikh funktsii formulami”, Matem. zametki, 11:1 (1972), 109–120 | MR | Zbl

[3] Khrapchenko V.M., “Nekotorye otsenki dlya vremeni umnozheniya”, Problemy kibernetiki, 33, Nauka, M., 1978, 221–227 | MR

[4] Paterson M., Pippenger N., Zwick U., “Optimal carry save networks”, Boolean function complexity, London Math. Soc. Lect. Notes Ser., 169, Cambridge University Press, Cambridge, 1992, 174–201 | MR

[5] Sergeev I.S., “Verkhnie otsenki slozhnosti formul dlya simmetricheskikh bulevykh funktsii”, Izv. vuzov. Matematika, 2014, no. 5, 38–52 | Zbl

[6] Sergeev I.S., “Verkhnie otsenki glubiny simmetricheskikh bulevykh funktsii”, Vestn. Mosk. un-ta. Ser. $15$, Vychisl. matem. i kibern., 2013, no. 4, 39–44 | Zbl

[7] Valiant L.G., “Short monotone formulae for the majority function”, J. Algorithms, 5 (1984), 363–366 ; Velyant L., “Prostye monotonnye formuly dlya funktsii golosovaniya”, Kibern. sb., 24, Mir, M., 1987, 97–100 | DOI | MR | Zbl

[8] Sinha R.K., Thathachar J.S., “Efficient oblivious branching programs for threshold and Mod functions”, J. Comput. and System Sci., 55:3 (1997), 373–384 | DOI | MR | Zbl

[9] Khrapchenko V.M., “Ob asimptoticheskoi otsenke vremeni slozheniya parallelnogo summatora”, Problemy kibernetiki, 19, Nauka, M., 1967, 107–120