О сложности монотонных схем для пороговых симметрических булевых функций

Показано, что сложность реализации монотонной симметрической булевой функции $n$ переменных с порогом $k = O(1)$ схемами над базисом $\{\vee,\, \wedge\}$ не превосходит $2 \log_2 k \cdot n + o(n)$. Кроме того, доказано, что сложность функции с порогом 2 равна $2n+\Theta(\sqrt n)$, а сложность функции с порогом 3 равна $3n+O(\log n)$ — установлены соответствующие нижние оценки.