On the complexity of linear Boolean operators with thin matrixes

S. B. Gashkov ; I. S. Sergeev

Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 3, pp. 3-18

Résumé

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.

Détail

Keywords: Boolean circuit, complexity, linear Boolean operator, finite field
Mots-clés : discrete Fourier transform, circulant matrix, Sidon set.