Upper bounds for the size and the depth of formulae for MOD-functions
Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 108-116
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{DM_2016_28_2_a9,
author = {I. S. Sergeev},
title = {Upper bounds for the size and the depth of formulae for {MOD-functions}},
journal = {Diskretnaya Matematika},
pages = {108--116},
publisher = {mathdoc},
volume = {28},
number = {2},
year = {2016},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DM_2016_28_2_a9/}
}
I. S. Sergeev. Upper bounds for the size and the depth of formulae for MOD-functions. Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 108-116. http://geodesic.mathdoc.fr/item/DM_2016_28_2_a9/