Upper bounds for the size and the depth of formulae for MOD-functions
Igor' Sergeevich Sergeev · Discrete Mathematics and Applications · 2017
Abstract We obtain new upper bounds for the size and the depth of formulae for some MOD-functions (that is, functions counting n bits modulo m ). In particular, the depth of counting n bits modulo 3 is bounded by 2.8 log 2 n + O (1) in the standard basis {Λ, V, — }; the size of counting modulo 5 is bounded by O ( n 3.22 ) in the same basis; the depth of counting modulo 7 is bounded by 2.93 log 2 n + O (1) in the basis of all binary Boolean functions.