Thin circulant matrices and lower bounds on the complexity of some Boolean operators

M. I. Grinchuk, I. S. Sergeev

We prove a lower bound $\Omega \left(\frac{k+l}{k^2{l}^2}{N}^{2-\frac{k+l+2}{kl}}\right)$ on the maximal possible weight of a $(k,l)$-free (that is, free of all-ones $k\times l$ submatrices)…