О средней сложности булевых функций, заданных полиномами Жегалкина

Рассматривается сложность реализации булевых функций, заданных полиномами Жегалкина степени не более $k$, неветвящимися программами с условной остановкой. Показано, что средняя сложность почти каждого полинома от $n$ переменных, степень которого не превосходит $k$, не меньше $\frac38\frac S{\log_2S}(1+o(1))$, где $S=\sum_{i=0}^k\binom ni$ и $n\to\infty$. Доказано, что для более половины значений $k$ средняя сложность каждого полинома от $n$ переменных степени $k$ не превосходит величины $(1/2)\frac S{\log_2 S}(1+o(1))$, $n\to\infty$.