Нижние оценки аддитивной сложности линейных операторов и билинейных алгоритмов умножения матриц и многочленов над $GF(2)$

Для линейного оператора с явно заданной булевой матрицей размера $n \times n$ установлена нижняя оценка сложности $5n-o(n)$ при реализации аддитивными схемами над $GF(2)$. Нижние оценки $3n-o(n)$ доказаны для конструктивно заданных циклических матриц и матриц Серпинского размера $n \times n$. Попутно установлены нижние оценки аддитивной сложности билинейных алгоритмов: $(4-o(1))n^2$ – для умножения матриц размера $n \times n$, а также $5n-o(n)$ – для умножения многочленов степени $n-1$ и $4n-o(n)$ – для циклической свертки порядка $n$ над $GF(2)$.
Библиография: 27 названий.