|
Discrete Functions
Some decompositions for quadratic Boolean threshold functions
A. N. Shurupov Moscow Technological University, Moscow
Abstract:
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<m^2$ 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 <i^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<l$ 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\}$.
Keywords:
quadratic Boolean threshold functions, decomposition.
Citation:
A. N. Shurupov, “Some decompositions for quadratic Boolean threshold functions”, Prikl. Diskr. Mat. Suppl., 2017, no. 10, 56–59
Linking options:
https://www.mathnet.ru/eng/pdma359 https://www.mathnet.ru/eng/pdma/y2017/i10/p56
|
|