EN|RU Volume 18, No 5, 2011, P. 38-53 UDC 519.7 M. I. Grinchuk, I. S. Sergeev Thin circulant matrixes and lower bounds on complexity of some boolean operators Abstract: Lower estimate $\Omega(\frac{k+l}{k^2l^2}N^{2-\frac{k+l+2}{kl}})$ of the maximal possible weight of a $(k,l)$-thin (that is, free of all-ones' submatrixes of size $k\times l$) circulant matrix of order $N$ is proved. The estimate is close to the known estimate corresponding to the class of all $(k,l)$-thin matrixes. As a consequence, new estimates of several complexity measures of Boolean sums' systems and a lower estimate $\Omega(N^2\log^{-6}N)$ of monotone complexity of a Boolean convolution of order $N$ are obtained. Ill. 1, bibliogr. 11. Keywords: complexity, circulant matrix, thin matrix, Zarankiewicz problem, monotone circuit, rectifier circuit, Boolean sum, Boolean convolution. Grinchuk Mikhail Ivanovich 1 Sergeev Igor Sergeevich 1 1. Lomonosov Moscow State University, Leninskie Gory, 119991 Moscow, Russia e-mail: grinchuk@nw.math.msu.su, isserg@gmail.com © Sobolev Institute of Mathematics, 2015