Lower Bounds for Additive Complexity of Linear Operators and Bilinear Algorithms for Matrix and Polynomial Multiplication over $$GF(2)$$
I. S. Sergeev · Mathematical Notes · 2025
For a linear operator with explicitly given Boolean $$n \times n$$ -matrix, we find the lower bound $$5n-o(n)$$ for complexity of implementation by additive circuits over $$GF(2)$$ . The lower bound $$3n-o(n)$$ is obtained for explicitly given circulant matrices and Sierpinski matrices of size $$n \times n$$ . In passing, we establish the following lower bounds for additive complexity of bilinear algorithms: $$(4-o(1))n^2$$ for multiplication of matrices of size $$n \times n$$ , $$5n-o(n)$$ for multiplication of polynomials of degree $$n-1$$ , and $$4n-o(n)$$ for the cyclic convolution of order $$n$$ over $$GF(2)$$ .