Geodesic
On the complexity of the realization of Zhegalkin polynomials
Diskretnaya Matematika, Tome 16 (2004) no. 1, pp. 79-94.

Voir la notice de l'article provenant de la source Math-Net.Ru

We show that the complexity of a Zhegalkin polynomial of degree $k$, $2\le k\le n$, does not exceed $$ \sum_{i=0}^{k}\binom ni/\log_2\sum_{i=0}^{k}\binom ni(1+o(1)), $$ (as $n\to\infty$) and asymptotically coincides with this number for almost all such polynomials. We also show that the complexity of any homogeneous Zhegalkin polynomial of degree $k$ (for most values of $k$) does not exceed $$ \binom nk/\log_2 \binom nk(1+o(1)), $$ (as $n\to\infty$) and asymptotically coincides with this number for almost all such polynomials. 
@article{DM_2004_16_1_a5,
     author = {R. N. Zabaluev},
     title = {On the complexity of the realization of {Zhegalkin} polynomials},
     journal = {Diskretnaya Matematika},
     pages = {79--94},
     publisher = {mathdoc},
     volume = {16},
     number = {1},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2004_16_1_a5/}
}
TY  - JOUR
AU  - R. N. Zabaluev
TI  - On the complexity of the realization of Zhegalkin polynomials
JO  - Diskretnaya Matematika
PY  - 2004
SP  - 79
EP  - 94
VL  - 16
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2004_16_1_a5/
LA  - ru
ID  - DM_2004_16_1_a5
ER  - 
%0 Journal Article
%A R. N. Zabaluev
%T On the complexity of the realization of Zhegalkin polynomials
%J Diskretnaya Matematika
%D 2004
%P 79-94
%V 16
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2004_16_1_a5/
%G ru
%F DM_2004_16_1_a5
R. N. Zabaluev. On the complexity of the realization of Zhegalkin polynomials. Diskretnaya Matematika, Tome 16 (2004) no. 1, pp. 79-94. http://geodesic.mathdoc.fr/item/DM_2004_16_1_a5/

[1] Kochergin V. V., “O slozhnosti vychislenii v konechnykh abelevykh gruppakh”, Matem. voprosy kibern., 4 (1990), 178–217

[2] Lipatov E. P., “Ob odnom sluchae neravnomernogo lokalnogo kodirovaniya”, Probl. kibern., 26 (1977), 95–107 | MR

[3] Lupanov O. B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem – printsipe lokalnogo kodirovaniya”, Probl. kibern., 14 (1965), 31–110 | MR | Zbl

[4] Lupanov O. B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Probl. kibern., 10 (1963), 63–97 | MR | Zbl

[5] Pippenger N., “On the evaluation of powers and monomials”, SIAM J. Comput., 9 (1980), 230–250 | DOI | MR | Zbl