Geodesic
On the Existence and Properties of Convex Extensions of Boolean Functions
Matematičeskie zametki, Tome 115 (2024) no. 4, pp. 533-551

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

We study the problem of the existence of a convex extension of any Boolean function $f(x_1,x_2,\dots,x_n)$ to the set $[0,1]^n$. A convex extension $f_C(x_1,x_2,\dots,x_n)$ of an arbitrary Boolean function $f(x_1,x_2,\dots,x_n)$ to the set $[0,1]^n$ is constructed. On the basis of a single convex extension $f_C(x_1,x_2,\dots,x_n)$, it is proved that any Boolean function $f(x_1,x_2,\dots,x_n)$ has infinitely many convex extensions to $[0,1]^n$. Moreover, it is proved constructively that, for any Boolean function $f(x_1,x_2,\dots,x_n)$, there exists a unique function $f_{DM}(x_1,x_2,\dots,x_n)$ being its maximal convex extensions to $[0,1]^n$.
Keywords: Boolean function, convex extension of a Boolean function, convex function, global optimization, local minimum. 
D. N. Barotov. On the Existence and Properties of Convex Extensions of Boolean Functions. Matematičeskie zametki, Tome 115 (2024) no. 4, pp. 533-551. http://geodesic.mathdoc.fr/item/MZM_2024_115_4_a4/
@article{MZM_2024_115_4_a4,
     author = {D. N. Barotov},
     title = {On the {Existence} and {Properties} of {Convex} {Extensions} of {Boolean} {Functions}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {533--551},
     year = {2024},
     volume = {115},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2024_115_4_a4/}
}
TY  - JOUR
AU  - D. N. Barotov
TI  - On the Existence and Properties of Convex Extensions of Boolean Functions
JO  - Matematičeskie zametki
PY  - 2024
SP  - 533
EP  - 551
VL  - 115
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/MZM_2024_115_4_a4/
LA  - ru
ID  - MZM_2024_115_4_a4
ER  - 
%0 Journal Article
%A D. N. Barotov
%T On the Existence and Properties of Convex Extensions of Boolean Functions
%J Matematičeskie zametki
%D 2024
%P 533-551
%V 115
%N 4
%U http://geodesic.mathdoc.fr/item/MZM_2024_115_4_a4/
%G ru
%F MZM_2024_115_4_a4

[1] A. H. Abdel-Gawad, A. F. Atiya, N. M. Darwish, “Solution of systems of Boolean equations via the integer domain”, Inform. Sci., 180:2 (2010), 288–300 | DOI | MR

[2] D. N. Barotov, R. N. Barotov, “Polylinear transformation method for solving systems of logical equations”, Mathematics, 10:6, 918 | DOI

[3] D. N. Barotov, “Target function without local minimum for systems of logical equations with a unique solution”, Mathematics, 10:12 (2022), 2097 | DOI

[4] J. A. Armario, “Boolean functions and permanents of Sylvester–Hadamard matrices”, Mathematics, 9:2 (2021), 177 | DOI | MR

[5] L. G. Valiant, “The complexity of computing the permanent”, Theoret. Comput. Sci., 8:2 (1979), 189–201 | DOI | MR

[6] R. T. Faizullin, V. I. Dulkeit, Yu. Yu. Ogorodnikov, “Gibridnyi metod poiska priblizhennogo resheniya zadachi $3$-vypolnimost, assotsiirovannoi s zadachei faktorizatsii”, Tr. IMM UrO RAN, 19:2 (2013), 285–294 | MR

[7] J. Gu, “Global optimization for satisfiability (SAT) problem”, IEEE Trans. Knowledge and DataEng., 6:3 (1994), 361–381 | DOI

[8] J. Gu, Q. Gu, D. Du, “On optimizing the satisfiability (SAT) problem”, J. Comput. Sci. Tech., 14:1 (1999), 1–17 | DOI | MR

[9] A. I. Pakhomchik, V. V. Voloshinov, V. M. Vinokur, G. B. Lesovik, “Converting of Boolean expression to linear equations, inequalities and QUBO penalties for cryptanalysis”, Algorithms, 15:2 (2022), 33 | DOI

[10] D. N. Barotov, R. N. Barotov, V. Soloviev, V. Feklin, D. Muzafarov, T. Ergashboev, Kh. Egamov, “The development of suitable inequalities and their application to systems of logical equations”, Mathematics, 10:11 (2022), 1851 | DOI

[11] D. N. Barotov, R. N. Barotov, “Polilineinye prodolzheniya nekotorykh diskretnykh funktsii i algoritm ikh nakhozhdeniya”, Vych. met. programmirovanie, 24:1 (2023), 10–23 | DOI

[12] D. N. Barotov, A. Osipov, S. Korchagin, E. Pleshakova, D. Muzafarov, R. Barotov, D. Serdechnyy, “Transformation method for solving system of Boolean algebraic equations”, Mathematics, 9:24 (2021), 3299 | DOI

[13] G. Owen, “Multilinear extensions of games”, Management Sci., 18(5-part-2) (1972), 64–79 | DOI | MR

[14] D. M. Wittmann, J. Krumsiek, J. Saez-Rodriguez, D. A. Lauffenburger, S. Klamt, F. J. Theis, “Transforming Boolean models to continuous models: methodology and application to T-cell receptor signaling”, BMC Systems Biology, 3:1 (2009), 1–21 | DOI | MR

[15] J. L. W. V. Jensen, “Sur les fonctions convexes et les inégalités entre les valeurs moyennes”, Acta Math., 30:1 (1906), 175–193 | DOI | MR