Some decompositions for quadratic Boolean threshold functions

A. N. Shurupov

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 56-59

Résumé

Arbitrary quadratic Boolean threshold functions $f$ defined by a quadratic form $w(x_1,\dots,x_n)=e(x_1,\dots,x_m)+a(x_{m+1},\dots,x_n)$ and a threshold $t$ are considered together with the quadratic forms $e$ and $a$ defined by the corresponding constant matrices $1_m$ and $a_{n-m}$. We propose a criterion for existence of a non-trivial decomposition of such a function $f$, namely: such a decomposition exists if and only if any of the following conditions holds: 1) $t$ and there exists $j$ in $\{1,\dots,n-m\}$ such that $\lfloor t\rfloor_e+a{(j-1)}^2\le t\lceil t\rceil_e$; 2) $t>m^2$ and there exist $i$ in $\{1,\dots,m\}$ and $j$ in $\{1,\dots,n-m\}$ such that $$ \max\{(i-1)^2+a(n-m)^2,m^2+a(j-1)^2\}\le t ^2+aj^2; $$ 3) $t>m^2$ and there exist $i$ in $\{1,\dots,m\}$, $j$ and $l$ in $\{1,\dots,n-m\}$ such that $j$ and $$ \max\{(i-1)^2+a(l-1)^2,m^2+a(j-1)^2\}\le t\min\{al^2,i^2+aj^2\}, $$ where $\lfloor t\rfloor_e=\max\{z\colon z=e(x),\ x\in\{0,1\}^m,\ z\le t\}$, $\lceil t\rceil_e=\min\{z\colon z=e(x),\ x\in\{0,1\}^m,\ z>t\}$.

Détail

Keywords: quadratic Boolean threshold functions
Mots-clés : decomposition.