Approximate polymorphisms

Gilad Chase, Yuval Filmus, Dor Minzer +2

For a function $g:\{0,1{\}}^m\to \{0,1\}$, a function $f:\{0,1{\}}^n\to \{0,1\}$ is called a $g$-polymorphism if their actions commute: $f(g(\mathsf{row}_1(Z)),\ldots,g(\maths…