О сложности реализации полиномов Жегалкина

Показано, что сложность полинома Жегалкина степени $k$, $2\le k\le n$, не превосходит величины
$$ \sum_{i=0}^{k}C_n^i/\log_2\sum_{i=0}^{k}C_n^i(1+o(1)), $$
(при $n\to\infty$) и для почти всех таких полиномов сложность асимптотически совпадает с этой величиной. Также показано, что сложность каждого однородного полинома Жегалкина степени $k$ (для большинства значений $k$) не превосходит величины
$$ C_n^k/\log_2 C_n^k(1+o(1)), $$
(при $n\to\infty$) и для почти всех таких полиномов сложность асимптотически совпадает с этой величиной.