О сложности линейных булевых операторов с редкими матрицами

Рассматривается задача построения квадратной булевой матрицы $A$ порядка $n$ без “прямоугольников” (такой матрицы, что составленная из её элементов, находящихся в каких-либо двух строках и двух столбцах, матрица не состоит из единиц), линейное преобразование по модулю два, определяемое которой, имеет сложность $o(\nu(A)-n)$ над базисом $\{\oplus\}$, где $\nu(A)$ – вес матрицы $A$, т.е. число единиц (такие матрицы без прямоугольников названы редкими матрицами). Приведены две конструкции, решающие данную задачу. В первой конструкции $n=p^2$, где $p$ – нечётное простое число. Соответствующая матрица $H_p$ имеет вес $p^3$ и порождает линейное преобразование сложности $O(p^2\log p\log\log p)$. Во второй конструкции матрица имеет вес $nk$, где $k$ – мощность множества Сидона в $\mathbb Z_n$. Можно считать, что $k=\Theta(\sqrt n)$, для некоторых $n$ известны примеры множеств мощности $k\sim\sqrt n$. При этом соответствующее линейное преобразование имеет сложность $O(n\log n\log\log n)$. Рассмотрены обобщения указанной задачи. Библиогр. 29.