|
This article is cited in 1 scientific paper (total in 1 paper)
Upper bounds for the size and the depth of formulae for MOD-functions
I. S. Sergeev Research Institute "Kvant"
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.
Received: 26.09.2015
Citation:
I. S. Sergeev, “Upper bounds for the size and the depth of formulae for MOD-functions”, Diskr. Mat., 28:2 (2016), 108–116; Discrete Math. Appl., 27:1 (2017), 15–22
Linking options:
https://www.mathnet.ru/eng/dm1373https://doi.org/10.4213/dm1373 https://www.mathnet.ru/eng/dm/v28/i2/p108
|
|