Complexity and depth of formulas for symmetric Boolean functions

I. S. Sergeev

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2016), pp. 53-57

Résumé

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$.