Geodesic
On the Existence and Properties of Convex Extensions of Boolean Functions
Matematičeskie zametki, Tome 115 (2024) no. 4, pp. 533-551 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@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
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/

[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