Approximate polymorphisms

For a function $g\text{\hspace{0.17em}⁣}:\{0,1{\}}^m\to \{0,1\}$, a function $f\colon {0,1}^n\to{0,1}$iscalleda$g$-polymorphismiftheiractionscommute:$f(g($\mathsf{r}\mathsf{o}\mathsf{w}$_1(Z)),\ldots,g($\mathsf{r}\mathsf{o}\mathsf{w}$_n(Z))) = g(f($\mathsf{c}\mathsf{o}\mathsf{l}$_1(Z)),\ldots,f($\mathsf{c}\mathsf{o}\mathsf{l}$_m(Z)))$forall$Z\in{0,1}^{n\times m}$\mathrm{.}Thefunction$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{A}\mathsf{N}\mathsf{D}$, $\mathsf{X}\mathsf{O}\mathsf{R}$, $\mathsf{O}\mathsf{R}$, $\mathsf{N}\mathsf{X}\mathsf{O}\mathsf{R}$$ 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\wedge y)=f(x)\wedge f(y)$ with probability larger than $s_{\wedge }\approx 0.815$ then $f$ correlates with some low-degree character, and $s_{\wedge }$ 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{X}\mathsf{O}\mathsf{R}$ 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.