Geodesic
Formula Complexity of a Linear Function in a $k$-ary Basis
Matematičeskie zametki, Tome 109 (2021) no. 3, pp. 419-435

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

A way of extending the Khrapchenko method of finding a lower bound for the complexity of binary formulas to formulas in $k$-ary bases is proposed. The resulting extension makes it possible to evaluate the complexity of a linear Boolean function and a majority function of $n$ variables when realized by formulas in the basis of all $k$-ary monotone functions and negation as $\Omega(n^{g(k)})$, where $g (k)=1+\Theta(1/\ln k)$. For a linear function, the complexity bound in this form is unimprovable. For $k=3$, the sharper lower bound $\Omega(n^{1.53})$ is proved.
Keywords: Boolean formulas, linear function, majority function, bipartite graphs, lower bounds for complexity.
Mots-clés : Khrapchenko method 
@article{MZM_2021_109_3_a8,
     author = {I. S. Sergeev},
     title = {Formula {Complexity} of a {Linear} {Function} in a $k$-ary {Basis}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {419--435},
     publisher = {mathdoc},
     volume = {109},
     number = {3},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2021_109_3_a8/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - Formula Complexity of a Linear Function in a $k$-ary Basis
JO  - Matematičeskie zametki
PY  - 2021
SP  - 419
EP  - 435
VL  - 109
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2021_109_3_a8/
LA  - ru
ID  - MZM_2021_109_3_a8
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T Formula Complexity of a Linear Function in a $k$-ary Basis
%J Matematičeskie zametki
%D 2021
%P 419-435
%V 109
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2021_109_3_a8/
%G ru
%F MZM_2021_109_3_a8
I. S. Sergeev. Formula Complexity of a Linear Function in a $k$-ary Basis. Matematičeskie zametki, Tome 109 (2021) no. 3, pp. 419-435. http://geodesic.mathdoc.fr/item/MZM_2021_109_3_a8/