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

Доказана нижняя оценка $\Omega(\frac{k+l}{k^2l^2}N^{2-\frac{k+l+2}{kl}})$ максимально возможного веса $(k,l)$-редкой (т.е. не содержащей единичных подматриц размера $k\times l$) циркулянтной матрицы порядка $N$. Эта оценка близка к известной оценке для класса всех $(k,l)$-редких матриц. В качестве следствия получены новые нижние оценки для нескольких мер сложности систем булевых сумм и нижняя оценка $\Omega(N^2\log^{-6}N)$ монотонной сложности булевой свёртки порядка $N$. Ил. 1, библиогр. 11.