О СЛОЖНОСТИ ЛИНЕЙНЫХ БУЛЕВЫХ ОПЕРАТОРОВ С РЕДКИМИ МАТРИЦАМИ
Рассматривается задача построения квадратной булевой матрицы A порядка n без «прямоугольников» (такой матрицы, что составленная из ее элементов, находящихся в каких-либо двух строках и двух столбцах, матрица не состоит из единиц), линейное преобразование по модулю два, определяемое которой, имеет сложность o(v(A) - n) над базисом {⊕}, где v(A) - вес матрицы A, т. е. число единиц (такие матрицы без прямоугольников названы редкими матрицами). Приведены две конструкции, решающие данную задачу. В первой конструкции n = ρ2, где ρ - нечетное простое число. Соответствующая матрица Hp имеет вес ρ3 и порождает линейное преобразование сложности O(ρ2 log ρ log log ρ). Во второй конструкции матрица имеет вес nk, где k - мощность множества Сидона в Zn. Можно считать, что k = Θ(√n), для некоторых n известны примеры множеств мощности k ~ √n. При этом соответствующее линейное преобразование имеет сложность O(n log n log log n). Рассмотрены обобщения указанной задачи.