Approximate polymorphisms

DOI10.1145/3519935.3519966MaRDI QIDQ6083476zbMATH OpenOpenAlexFDO

Authors Yuval Filmus, Dor Minzer, Elchanan Mossel, Nitin Saurabh

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.00093

zbMATH Keywords

polymorphismsproperty testingsocial choice theory

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: For a function $gcolon{0,1}^{m}o0,1$, a function $fcolon{0,1}^{n}o0,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 $Zin{0,1}^{nimesm}$. 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=mathsfAND,mathsfXOR,mathsfOR,mathsfNXOR$ 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(xlandy)=f(x)landf(y)$ with probability larger than $s_{l}andapprox0.815$ then $f$ correlates with some low-degree character, and $s_{l}and$ 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=mathsfXOR$ 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.

Cited in

(4)

• Polymorphism and apartness
• A full continuous model of polymorphism
• On approximability of satisfiable k-CSPs: II
• Testing intersecting and union-closed families

This page was built for publication: Approximate polymorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083476)