|
Diskretnyi Analiz i Issledovanie Operatsii, 2011, Volume 18, Issue 5, Pages 38–53
(Mi da664)
|
|
|
|
This article is cited in 4 scientific papers (total in 4 papers)
Thin circulant matrixes and lower bounds on complexity of some Boolean operators
M. I. Grinchuk, I. S. Sergeev Lomonosov Moscow State University, Moscow, Russia
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.
Received: 27.01.2011
Citation:
M. I. Grinchuk, I. S. Sergeev, “Thin circulant matrixes and lower bounds on complexity of some Boolean operators”, Diskretn. Anal. Issled. Oper., 18:5 (2011), 38–53
Linking options:
https://www.mathnet.ru/eng/da664 https://www.mathnet.ru/eng/da/v18/i5/p38
|
Statistics & downloads: |
Abstract page: | 528 | Full-text PDF : | 130 | References: | 45 | First page: | 8 |
|