О сложности реализации линейной функции формулами в конечных булевых базисах

В работе полностью описано множество базисов, сложность реализации в которых функции $x_1\oplus\ldots\oplus x_n$ по порядку равна $n$. Для всех базисов, не принадлежащих этому множеству, получена нижняя оценка сложности реализации функции $x_1\oplus\ldots\oplus x_n$, имеющая вид $n^c$, где $c>1$ и $c$ не зависит от $n$. Опираясь на полученную оценку сложности, дано более простое доказательство существования бесконечной цепи улучшающихся булевых базисов.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 99–01–01175, и ФЦП «Интеграция», проект 473.