Geodesic
Lower bounds on the formula complexity of a linear Boolean function
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 165-184.

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

Given proof of the lower boundaries of the computational complexity of the linear Boolean function $x_1+\ldots+x_n=1 \pmod 2$ by formulas in the basis $\{\vee,\wedge,^-\}$. It is proved that for $n=6$ this complexity is not less than 40. Earlier, this result was obtained Cherukhin with use of computer calculations [1]. Given a simplified proof of the lower bound, published at [2]: for even $n\neq2^k$ the complexity is not less than $n^2+2$, for odd $n\geq5$ the complexity is not less than $n^2+3$.
Keywords: lower bounds on the formula complexity, formulas, $\pi$-schemes. 
@article{SEMR_2014_11_a48,
     author = {K. L. Rychkov},
     title = {Lower bounds on the formula complexity of a linear {Boolean} function},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {165--184},
     publisher = {mathdoc},
     volume = {11},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2014_11_a48/}
}
TY  - JOUR
AU  - K. L. Rychkov
TI  - Lower bounds on the formula complexity of a linear Boolean function
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2014
SP  - 165
EP  - 184
VL  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2014_11_a48/
LA  - ru
ID  - SEMR_2014_11_a48
ER  - 
%0 Journal Article
%A K. L. Rychkov
%T Lower bounds on the formula complexity of a linear Boolean function
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2014
%P 165-184
%V 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2014_11_a48/
%G ru
%F SEMR_2014_11_a48
K. L. Rychkov. Lower bounds on the formula complexity of a linear Boolean function. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 165-184. http://geodesic.mathdoc.fr/item/SEMR_2014_11_a48/

[1] D. Yu. Cherukhin, “K voprosu o logicheskom predstavlenii schëtchika chëtnosti”, Neformalnaya nauka, 2 (2008), 14–23

[2] K. L. Rychkov, “O nizhnikh otsenkakh slozhnosti parallelno-posledovatelnykh kontaktnykh skhem, realizuyuschikh lineinye bulevy funktsii”, Sibirskii zhurnal issledovaniya operatsii, 1:4 (1994), 33–52 | MR | Zbl

[3] S. V. Yablonskii, “Realizatsiya lineinoi funktsii v klasse P-skhem”, DAN SSSR, 94:5 (1954), 805–806 | MR

[4] V. M. Khrapchenko, “O slozhnosti realizatsii lineinoi funktsii v klasse P-skhem”, Matem. zametki, 9:1 (1971), 35–40 | Zbl

[5] B. A. Subbotovskaya, “O realizatsii lineinykh funktsii formulami v bazise $\vee$, $\wedge$, ${}^-$”, DAN SSSR, 136:3 (1961), 553–555 | Zbl

[6] R. G. Nigmatulin, Slozhnost bulevykh funktsii, Nauka, M., 1991 | MR