PublicationsManuscripts

We determine all $n$-ary Boolean functions $f_0,\ldots,f_m$ and $m$-ary Boolean functions $g_0,\ldots,g_n$ satisfying the equation
$f_0(g_1(z_{11},\ldots,z_{1m}),\ldots,g_n(z_{n1},\ldots,z_{nm})) =
g_0(f_1(z_{11},\ldots,z_{n1}),\ldots,f_m(z_{1m},\ldots,z_{nm}))$,
for all Boolean inputs ${ z_{ij} : i \in [n], j \in [m] }$. When the functions $f_0,\ldots,f_m,g_0,\ldots,g_n$ satisfy the above, we refer to them as a generalized polymorphism. This characterization generalizes a previously known characterization for polymorphisms, which are the special case of generalized polymorphisms formed by letting $g_1 = \dots = g_n$.

Our characterization not only captures the previously known characterization of polymorphisms, but also consolidates its case-wise characterization statement into a single consolidated expression. Indeed, this was made possible by viewing polymorphisms in the more general setting of generalized polymorphisms, which revealed a structure previously hidden due to degeneracies imposed by the assumption $g_1 = \dots = g_n$.

The characterization we obtain generalizes the previously known characterization of polymorphisms in two major aspects: first, we show that every generalized polymorphism is essentially composed of an evaluation of an arbitrary Boolean
function $h$ whose inputs are substituted with
$k$ polymorphisms, derived from $k$ disjoint
subsections of the input space. For polymorphisms, this partition degenerates into a singleton, and $h$ degenerates into simply returning the result of the polymorphism, up to sign. We show this aspect of our characterization in isolation, by restricting our inputs to include only functions of degree at least 2. The second aspect in which our characterization generalizes that of polymorphisms is the prevalence of arbitrary evaluations for certain subproblems involving degree 1 functions. For polymorphisms, this type of evaluation occurs in only two types of solutions. In contrast, in our characterization, it permeates throughout all solutions. We show this aspect after showing the first described above, by lifting the degree constraint imposed therein and generalizing the results achieved there using similar methods.