Том 17, номер 3, 2010 г., Стр. 3-18

УДК 519.7, 519.61
Гашков С. Б., Сергеев И. С.
О сложности линейных булевых операторов с редкими матрицами

Аннотация:
Рассматривается задача построения квадратной булевой матрицы $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.

Ключевые слова: булева схема, сложность, линейный булев оператор, дискретное преобразование Фурье, конечное поле, циркулянтная матрица, множество Сидона.

Гашков Сергей Борисович ¹
Сергеев Игорь Сергеевич ¹
1. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 119991 Москва, Россия
е-mail: sbgashkov@gmail.com, isserg@gmail.com

Статья поступила 22 октября 2009 г.