RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2016 Volume 28, Issue 2, Pages 108–116 (Mi dm1373)

This article is cited 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.

UDC: 519.714.7

Received: 26.09.2015

DOI: 10.4213/dm1373


 English version:
Discrete Mathematics and Applications, 2017, 27:1, 15–22

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025