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 ¹
Sergeev Igor Sergeevich ¹
1. Lomonosov Moscow State University,
Leninskie Gory, 119991 Moscow, Russia
e-mail: grinchuk@nw.math.msu.su, isserg@gmail.com