Some decompositions for quadratic boolean threshold functions

Arbitrary quadratic Boolean threshold functions f defined by a quadratic form w(xi,..., = e(xi,..., x_m) + a(x_m+1,..., 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² and there exists j in {1,..., n - m} such that |_tj_e + a(j - 1)² ^ t < |Y|_e; 2) t > m² and there exist i in {1,..., m} and j in {1,..., n - m} such that max{(i - 1)² + a(n - m)²,m² + a(j - 1)²} ^ t < i² + aj²; 3) t > m² and there exist i in {1,..., m}, j and l in {1,..., n - m} such that j < l and max{(i - 1)² + a(l - 1)², m² + a(j - 1)²} ^ t < min{al², i² + aj²}, where |_tj_e = max{z : z = e(x),x G {0,1}^m,z ^ t}, [t|_e = min{z : z = e(x),x G {0,1}^m, z > t}.

Keywords

Authors

References