Approximate polymorphisms

For a function g : 0, 1 m → 0, 1, a function f : 0, 1 n → 0, 1 is called a g-polymorphism if their actions commute: f (g(row1(Z)), . . . , g(rown(Z))) = g(f (col1(Z)), . . . , f (colm(Z))) for all Z ∈ 0, 1 n×m . The function f is called an approximate g-polymorphism if this equality holds with probability close to 1, when Z is sampled uniformly. A pair of functions f0, f1 : 0,

We study the structure of exact polymorphisms as well as approximate polymorphisms. Our results include:

1. We prove that an approximate polymorphism f must be close to an exact skew polymorphism; 2. We give a characterization of exact skew polymorphisms, showing that besides trivial cases, only the functions g = AND, XOR, OR, NAND, NOR, NXOR admit non-trivial exact skew 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 ∧ y) = f (x) ∧ f (y) with probability larger than s∧ ≈ 0.815 then f correlates with some low-degree character, and s∧ 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 = 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.