Volume 17, No 3, 2010, P. 318
UDC 519.7, 519.61
S. B. Gashkov and I. S. Sergeev
On the complexity of linear boolean operators with thin matrixes
Abstract:
It is considered the problem of construction of a “rectanglefree” Boolean $(n\times n)$matrix $A$ (i.e. a matrix without ($2\times2$)submatrixes of all unities) such that the corresponding linear mapping modulo 2 has complexity $o(\nu(A)n)$ in the basis $\{\oplus\}$, where $\nu(A)$ is the weight of $A$, i.e. the number of unities. (In the paper by Mityagin and Sadovskiy (1965), where the problem was originally studied, “rectanglefree” matrixes were called thin matrixes.) Two constructions for solving the problem are introduced. In the first example $n=p^2$, where $p$ is an odd prime number. The weight of the corresponding matrix $H_p$ is $p^3$ and the complexity of the corresponding linear operator is $O(p^2\log p\log\log p)$. The matrix in the second example has weight $nk$, where $k$ is the cardinality of the Sidon set in $\mathbb Z_n$. One can put $k=\Theta(\sqrt n)$; for some $n$, Sidon sets of cardinality $k\sim\sqrt n$ are known. The complexity of the corresponding linear mapping is $O(n\log n\log\log n)$. Some generalizations of the problem are also considered.
Bibl. 29.
Keywords: Boolean circuit, complexity, linear Boolean operator, discrete Fourier transform, finite field, circulant matrix, Sidon set.
Gashkov Sergei Borisovich ^{1}
Sergeev Igor Sergeevich ^{1}
1. Lomonosov Moscow State University,
Leninskie gory, 119991 Moscow, Russia
email: sbgashkov@gmail.com, isserg@gmail.com
