On the complexity of the realization of Zhegalkin polynomials

R. N. Zabaluev

Diskretnaya Matematika, Tome 16 (2004) no. 1, pp. 79-94

Résumé

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.