  For a function $g\colon\{0,1\}^m\to\{0,1\}$, a function $f\colon
\{0,1\}^n\to\{0,1\}$ is called a $g$-polymorphism if their actions commute:
$f(g(\mathsf{row}_1(Z)),\ldots,g(\mathsf{row}_n(Z))) =
g(f(\mathsf{col}_1(Z)),\ldots,f(\mathsf{col}_m(Z)))$ for all
$Z\in\{0,1\}^{n\times m}$. The function $f$ is called an approximate
polymorphism if this equality holds with probability close to $1$, when $Z$ is
sampled uniformly.
  We study the structure of exact polymorphisms as well as approximate
polymorphisms. Our results include:
  - We prove that an approximate polymorphism $f$ must be close to an exact
polymorphism;
  - We give a characterization of exact polymorphisms, showing that besides
trivial cases, only the functions $g = \mathsf{AND}, \mathsf{XOR}, \mathsf{OR},
\mathsf{NXOR}$ admit non-trivial exact polymorphisms.
  We also study the approximate polymorphism problem in the list-decoding
regime (i.e., when the probability equality holds is not close to $1$, but is
bounded away from some value). We show that if $f(x \land y) = f(x) \land f(y)$
with probability larger than $s_\land \approx 0.815$ then $f$ correlates with
some low-degree character, and $s_\land$ is the optimal threshold for this
property.
  Our result generalize the classical linearity testing result of Blum, Luby
and Rubinfeld, that in this language showed that the approximate polymorphisms
of $g = \mathsf{XOR}$ are close to XOR's, as well as a recent result of Filmus,
Lifshitz, Minzer and Mossel, showing that the approximate polymorphisms of AND
can only be close to AND functions.
