On the complexity of the realization of Zhegalkin polynomials
Diskretnaya Matematika, Tome 16 (2004) no. 1, pp. 79-94
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},
year = {2004},
volume = {16},
number = {1},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/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