Geodesic
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/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - Upper bounds for the size and the depth of formulae for MOD-functions
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 108
EP  - 116
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_2_a9/
LA  - ru
ID  - DM_2016_28_2_a9
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T Upper bounds for the size and the depth of formulae for MOD-functions
%J Diskretnaya Matematika
%D 2016
%P 108-116
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_2_a9/
%G ru
%F 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/

[1] Lupanov O. B., “K voprosu o realizatsii simmetricheskikh funktsii algebry logiki kontaktnymi skhemami”, Problemy kibernetiki. Vyp. $15$, Nauka, Moskva, 1965, 85–99 | MR

[2] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, Moskva, 1984, 138 pp.

[3] Jukna S., Boolean Function Complexity, Springer-Verlag, Berlin, Heidelberg, 2012, 618 pp. | MR | Zbl

[4] Sergeev I. S., “Verkhnie otsenki glubiny simmetricheskikh bulevykh funktsii”, Vestnik MGU. Ser. $15$. Vychisl. matem. i kibernetika, 2013, no. 4, 39–44 | MR | Zbl

[5] Sergeev I. S., “Verkhnie otsenki slozhnosti formul dlya simmetricheskikh bulevykh funktsii”, Izvestiya vysshikh uchebnykh zavedenii. Matematika, 2014, no. 5, 38–52 | Zbl

[6] Fischer M. J., Meyer A. R., Paterson M. S., “$\Omega(n \log n)$ lower bounds on length of Boolean formulas”, SIAM J. Comput., 11:3 (1982), 416–427 | DOI | MR | Zbl

[7] Khrapchenko V. M., “Ob odnom metode polucheniya nizhnikh otsenok slozhnosti $\pi$-skhem”, Matematicheskie zametki, 10:1 (1971), 83–92 | Zbl

[8] van Leijenhorst D. C., “A note on the formula size of the “mod k” functions”, Inf. Process. Lett., 24 (1987), 223–224 | DOI | MR | Zbl

[9] Chin A., “On the depth complexity of the counting functions”, Inf. Process. Lett., 35 (1990), 325–328 | DOI | MR | Zbl

[10] Kojevnikov A., Kulikov A. S., Yaroslavtsev G., “Finding efficient circuits using SAT-solvers”, Proc. $12$th SAT, Lect. Notes Comput. Sci., 5584 (2009), 139–157, Springer

[11] McColl W. F., Some results on circuit depth, Theory of computation. Report No. 18, Univ. of Warwick, Coventry, 1977

[12] Sergeev I. S., “O slozhnosti i glubine formul dlya simmetricheskikh bulevykh funktsii”, Vestnik Mosk. un-ta. Ser. 1: Mat. Mekh., 2016, no. 3, 53–57