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 $\{ \wedge, \vee, \overline{\phantom{a}} \}$; 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.
Keywords:symmetric Boolean function, depth, formula size.