Abstract
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)\) .
