Approximate polymorphisms of predicates

Abstract

A generalized polymorphism of a predicate $P\subseteq \{0,1{\}}^m$ is a tuple of functions $f_1,\dots ,f_m:\{0,1{\}}^n\to \{0,1\}$ satisfying the following property: If $x^{(1)},\dots ,x^{(m)}\in \{0,1{\}}^n$ are such that $(x_i^{(1)},\dots ,x_i^{(m)})\in P$ for all $i$, then also $(f_1(x^{(1)}),\dots ,f_m(x^{(m)}))\in P$. We show that if $f_1,\dots ,f_m$ satisfy this property for most $x^{(1)},\dots ,x^{(m)}$ (as measured with respect to an arbitrary full support distribution $\hat{I}¼$ on $P$), then $f_1,\dots ,f_m$ are close to a generalized polymorphism of $P$ (with respect to the marginals of $\hat{I}¼$). Our main result generalizes several results in the literature: linearity testing, quantitative Arrow theorems, approximate intersecting families, AND testing, and more generally $f$-testing.

39 pages; corrected a mistake in the proof of Theorem 1.6