Geodesic
On complexity of linear operators on the class of circuits of depth~2
Diskretnaya Matematika, Tome 20 (2008) no. 1, pp. 109-119.

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

In this study we suggest methods for obtaining lower bounds for complexity of linear Boolean operators (and the related matrices) in two models of circuits of depth 2. In the first model, only linear elements with arbitrary number of inputs are allowed, whereas in the second one, any Boolean elements can be present. These methods are applicable to matrices with sufficiently large Hamming distance between the rows, for example, to the Hadamard matrices. 
@article{DM_2008_20_1_a9,
     author = {D. Yu. Cherukhin},
     title = {On complexity of linear operators on the class of circuits of depth~2},
     journal = {Diskretnaya Matematika},
     pages = {109--119},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2008_20_1_a9/}
}
TY  - JOUR
AU  - D. Yu. Cherukhin
TI  - On complexity of linear operators on the class of circuits of depth~2
JO  - Diskretnaya Matematika
PY  - 2008
SP  - 109
EP  - 119
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2008_20_1_a9/
LA  - ru
ID  - DM_2008_20_1_a9
ER  - 
%0 Journal Article
%A D. Yu. Cherukhin
%T On complexity of linear operators on the class of circuits of depth~2
%J Diskretnaya Matematika
%D 2008
%P 109-119
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2008_20_1_a9/
%G ru
%F DM_2008_20_1_a9
D. Yu. Cherukhin. On complexity of linear operators on the class of circuits of depth~2. Diskretnaya Matematika, Tome 20 (2008) no. 1, pp. 109-119. http://geodesic.mathdoc.fr/item/DM_2008_20_1_a9/

[1] Nigmatullin R. G., Slozhnost bulevykh funktsii, Nauka, Moskva, 1991 | MR | Zbl

[2] Nechiporuk E. I., “Ob odnoi bulevskoi matritse”, Probl. kibern., 21 (1969), 237–240 | Zbl

[3] Grinchuk M. I., “O slozhnosti realizatsii posledovatelnosti treugolnykh bulevykh matrits ventilnymi skhemami razlichnoi glubiny”, Metody diskretnogo analiza v sinteze upravlyayuschikh sistem, 44 (1986), 3–23 | MR | Zbl

[4] Alon N., Karchmer M., Wigderson A., “Linear circuits over $GF(2)$”, SIAM J. Comput., 19 (1990), 1064–1067 | DOI | MR | Zbl

[5] Pudlak P., “Communication in bounded depth circuits”, Combinatorica, 14:2 (1994), 203–216 | DOI | MR | Zbl

[6] Radhakrishnan J., Ta-Shma A., “Bounds for dispersers, extractors, and depth-two superconcentrators”, SIAM J. Discrete Math., 13:1 (2000), 2–24 | DOI | MR | Zbl

[7] Pudlak P., Savicky P., “On shifting networks”, Theoret. Comput. Sci., 116 (1993), 415–419 | DOI | MR | Zbl

[8] Pudlak P., Rödl V., Sgall J., “Boolean circuits, tensor ranks and communication complexity”, SIAM J. Comput., 26:3 (1997), 605–633 | DOI | MR | Zbl

[9] Raz R., Shpilka A., “Lower bounds for matrix product in bounded depth circuits with arbitrary gates”, SIAM J. Comput., 32:2 (2003), 488–513 | DOI | MR | Zbl

[10] Cherukhin D. Yu., “Nizhnyaya otsenka slozhnosti v klasse skhem glubiny 2 bez ogranichenii na bazis”, Vestnik Moskovskogo universiteta. Seriya 1. Matematika. Mekhanika, 2005, no. 4, 54–56 | MR