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.

UDC: 512.55

DOI: 10.17223/2226308X/10/24