Geodesic
Thin circulant matrixes and lower bounds on complexity of some Boolean operators
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 5, pp. 38-53.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, thin matrix, Zarankiewicz problem, Boolean sum
Mots-clés : circulant matrix, monotone circuit, rectifier circuit, Boolean convolution. 
@article{DA_2011_18_5_a2,
     author = {M. I. Grinchuk and I. S. Sergeev},
     title = {Thin circulant matrixes and lower bounds on complexity of some {Boolean} operators},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {38--53},
     publisher = {mathdoc},
     volume = {18},
     number = {5},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_5_a2/}
}
TY  - JOUR
AU  - M. I. Grinchuk
AU  - I. S. Sergeev
TI  - Thin circulant matrixes and lower bounds on complexity of some Boolean operators
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 38
EP  - 53
VL  - 18
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_5_a2/
LA  - ru
ID  - DA_2011_18_5_a2
ER  - 
%0 Journal Article
%A M. I. Grinchuk
%A I. S. Sergeev
%T Thin circulant matrixes and lower bounds on complexity of some Boolean operators
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 38-53
%V 18
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_5_a2/
%G ru
%F DA_2011_18_5_a2
M. I. Grinchuk; I. S. Sergeev. Thin circulant matrixes and lower bounds on complexity of some Boolean operators. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 5, pp. 38-53. http://geodesic.mathdoc.fr/item/DA_2011_18_5_a2/

[1] Gashkov S. B., Sergeev I. S., “O slozhnosti lineinykh bulevykh operatorov s redkimi matritsami”, Diskret. analiz i issled. operatsii, 17:3 (2010), 3–18 | MR

[2] Grinchuk M. I., “O slozhnosti realizatsii tsiklicheskikh bulevykh matrits ventilnymi skhemami”, Izv. vuzov. Matematika, 1988, no. 7, 39–44 | MR | Zbl

[3] Korshunov A. D., “Monotonnye bulevy funktsii”, Uspekhi mat. nauk, 58:5 (2003), 89–162 | MR | Zbl

[4] Lupanov O. B., “O ventilnykh i kontaktno-ventilnykh skhemakh”, Dokl. AN SSSR, 111:6 (1956), 1171–1174 | MR | Zbl

[5] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, M., 1984, 138 pp.

[6] Melkhorn K., “Nekotorye zamechaniya, kasayuschiesya bulevykh summ”, Kiberneticheskii sbornik, 18, Mir, M., 1981, 39–45

[7] Erdesh P., Spenser Dzh., Veroyatnostnye metody v kombinatorike, Mir, M., 1976, 130 pp. | MR

[8] Blum N., On negations in Boolean networks, Lect. Notes Comput. Sci., 5760, Springer-Verl., Berlin–Heidelberg, 2009, 18–29 | Zbl

[9] Gardner R. J., Gronchi P., “A Brunn–Minkowski inequality for the integer lattice”, Trans. Amer. Math. Soc., 353:10 (2001), 3995–4024 | DOI | MR | Zbl

[10] Ruzsa I. Z., “Sum of sets in several dimensions”, Combinatorica, 14 (1994), 485–490 | DOI | MR | Zbl

[11] Wegener I., The complexity of boolean functions, Wiley, Stuttgart, 1987, 470 pp. | MR | Zbl