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)$.
Keywords:additive circuit, bilinear algorithm, linear Boolean operator, Sierpinski matrix, Sidon set, lower bound for complexity, direct sum of matrices, matrix multiplication, polynomial multiplication, cyclic convolution, circulant matrix, cycle in graph.
Fulltext:
PDF file (773 kB)
First page:
PDF file
