Volume 17, No 3, 2010, P. 3-18

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 “rectangle-free” 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, “rectangle-free” 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 ¹
Sergeev Igor Sergeevich ¹
1. Lomonosov Moscow State University,
Leninskie gory, 119991 Moscow, Russia
e-mail: sbgashkov@gmail.com, isserg@gmail.com