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/