Geodesic
Complexity of the realization of a linear function in the class of $\Pi$-circuits
Matematičeskie zametki, Tome 9 (1971) no. 1, pp. 35-40

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

It is proved that the linear function $g_n(x_1,\dots,x_n)=x_1+\dots+x_n\mod2$ is realized in the class of $\Pi$-circuits with complexity $L_\pi(g_n)\geqslant n^2$. Combination of this result with S. V. Yablonskii's upper bound yields $L_\pi(g_n)\genfrac{}{}{0pt}{}{\smile}{\frown} n^2$. 
@article{MZM_1971_9_1_a4,
     author = {V. M. Khrapchenko},
     title = {Complexity of the realization of a linear function in the class of $\Pi$-circuits},
     journal = {Matemati\v{c}eskie zametki},
     pages = {35--40},
     publisher = {mathdoc},
     volume = {9},
     number = {1},
     year = {1971},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_1971_9_1_a4/}
}
TY  - JOUR
AU  - V. M. Khrapchenko
TI  - Complexity of the realization of a linear function in the class of $\Pi$-circuits
JO  - Matematičeskie zametki
PY  - 1971
SP  - 35
EP  - 40
VL  - 9
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_1971_9_1_a4/
LA  - ru
ID  - MZM_1971_9_1_a4
ER  - 
%0 Journal Article
%A V. M. Khrapchenko
%T Complexity of the realization of a linear function in the class of $\Pi$-circuits
%J Matematičeskie zametki
%D 1971
%P 35-40
%V 9
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_1971_9_1_a4/
%G ru
%F MZM_1971_9_1_a4
V. M. Khrapchenko. Complexity of the realization of a linear function in the class of $\Pi$-circuits. Matematičeskie zametki, Tome 9 (1971) no. 1, pp. 35-40. http://geodesic.mathdoc.fr/item/MZM_1971_9_1_a4/