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/

[1] V. M. Khrapchenko, “Ob odnom metode polucheniya nizhnikh otsenok slozhnosti $\Pi$-skhem”, Matem. zametki, 10:1 (1971), 83–92 | MR | Zbl

[2] B. A. Subbotovskaya, “O realizatsii lineinykh funktsii formulami v bazise $\vee$, $\$, $^-$”, Dokl. AN SSSR, 136:3 (1961), 553–555 | MR | Zbl

[3] B. A. Muchnik, “Otsenka slozhnosti realizatsii lineinoi funktsii formulami v nekotorykh bazisakh”, Kibernetika, 4 (1970), 29–38 | MR

[4] N. A. Peryazev, “Slozhnost predstavlenii bulevykh funktsii formulami v nemonolineinykh bazisakh”, Diskret. matem. i inform., 2, Izd-vo Irkutskogo un-ta, Irkutsk, 1995

[5] D. Yu. Cherukhin, “O slozhnosti realizatsii lineinoi funktsii formulami v konechnykh bulevykh bazisakh”, Diskret. matem., 12:1 (2000), 135–144 | DOI | MR | Zbl

[6] D. Yu. Cherukhin, “O skhemakh iz funktsionalnykh elementov konechnoi glubiny vetvleniya”, Diskret. matem., 18:4 (2006), 73–83 | DOI | MR | Zbl

[7] H. Chockler, U. Zwick, “Which bases admit non-trivial shrinkage of formulae?”, Comput. Complexity, 10 (2001), 28–40 | DOI | MR

[8] D. Yu. Cherukhin, “O realizatsii lineinoi funktsii formulami v razlichnykh bazisakh”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 2001, no. 6, 15–19 | MR | Zbl

[9] K. Ueno, “Formula complexity of ternary majorities”, Computing and Combinatorics, Lecture Notes in Comput. Sci., 7434, Springer, Heidelberg, 2012, 433–444 | MR

[10] I. S. Sergeev, “Verkhnie otsenki slozhnosti formul dlya simmetricheskikh bulevykh funktsii”, Izv. vuzov. Matem., 2014, no. 5, 38–52

[11] I. S. Sergeev, “O slozhnosti i glubine formul dlya simmetricheskikh bulevykh funktsii”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 2016, no. 3, 53–57 | MR

[12] M. M. Rokhlina, “O skhemakh, povyshayuschikh nadezhnost”, Problemy kibernetiki, 23, Nauka, M., 1970, 295–301 | MR

[13] A. Gupta, S. Mahajan, “Using amplification to compute majority with small majority gates”, Comput. Complexity, 6 (1996), 46–63 | DOI | MR

[14] S. Jukna, Boolean Function Complexity, Algorithms Combin., 27, Springer-Verlag, Berlin, 2012 | MR

[15] I. Wegener, Complexity of Boolean functions, B. G. Teubner, Stuttgart, 1987 | MR

[16] K. L. Rychkov, “Modifikatsiya metoda V. M. Khrapchenko i primenenie ee k otsenkam slozhnosti $\Pi$-skhem dlya kodovykh funktsii”, Metody diskretnogo analiza v teorii grafov i skhem, 42, IM SO AN SSSR, Novosibirsk, 1985, 91–98

[17] G. G. Khardi, Dzh. E. Littlvud, G. Polia, Neravenstva, IL, M., 1948 | MR | Zbl

[18] M. S. Paterson, N. Pippenger, U. Zwick, “Optimal carry save networks”, Boolean Function Complexity, London Math. Soc. Lecture Note Ser., 169, Cambridge Univ. Press, Cambridge, 1992, 174–201 | MR