ON THE COMPLEXITY OF LINEAR BOOLEAN OPERATORS WITH THIN MATRIXES
It is considered the problem of construction of a «rectangle-free» Boolean (n × n)-matrix A (i.e. a matrix without (2 × 2)-submatrixes of all unities) such that the corresponding linear mapping modulo 2 has complexity o(v(A) - n) in the basis {⊕}, where v(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 = ρ2, where ρ is an odd prime number. The weight of the corresponding matrix Hρ is ρ3 and the complexity of the corresponding linear operator is O(ρ2 log ρ log log ρ). The matrix in the second example has weight nk, where k is the cardinality of the Sidon set in Zn. One can put k = Θ(√n); for some n, Sidon sets of cardinality k ~ √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. 6.