Upper bounds for the size and the depth of formulae for MOD-functions

I. S. Sergeev

Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 108-116

Résumé

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.

Détail

Keywords: symmetric Boolean function, depth, formula size.