Complexity and depth of formulas for symmetric Boolean functions
Igor' Sergeevich Sergeev · Moscow University Mathematics Bulletin · 2016
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 = {∧, ∨,- } were non-constructively obtained. In particular, the depth of multiplication of n-bit binary numbers is asymptotically estimated from above by 4.02 log2 n relative to the basis B 2 and by 5.14log2 n relative to the basis B 0.