Complexity and Depth of Formulas for Symmetric Boolean Functions / I. S. Sergeev. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2016. № 3. P. 53-57 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 127-130].

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 \hbox{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.

Key words: Boolean formulae, formula size, depth, symmetric Boolean functions, multiplication.