Approximate polymorphisms

Chase, Gilad and Filmus, Yuval and Minzer, Dor and Mossel, Elchanan and Saurabh, Nitin (2022) Approximate polymorphisms. In: 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, 20 June 2022through 24 June 2022, Rome.

Text
Annual_ACM_Symposium.pdf - Published Version
Available under License Creative Commons Attribution.
Download (213kB)

Abstract

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,1}n → {0,1} are called a skew g-polymorphism if f0(g(row1(Z)) g(rown(Z))) = g(f1(col1(Z)) f1(colm(Z))) for all Z{0,1}n× m. We study the structure of exact polymorphisms as well as approximate polymorphisms. Our results include a proof that an approximate polymorphism f must be close to an exact skew polymorphism, and a characterization of exact skew polymorphisms, which shows that besides trivial cases, only the functions AND, XOR, OR, NAND, NOR, XNOR 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 junta, 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. © 2022 Owner/Author.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Saurabh, Nitin	https://orcid.org/0000-0002-1670-1114

Item Type:

Conference or Workshop Item (Paper)

Additional Information:

Gilad Chase, Yuval Filmus and Nitin Saurabh have received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 802020-ERC-HARMONIC.

Uncontrolled Keywords:

polymorphisms; property testing; social choice theory

Subjects:

Computer science

Divisions:

Department of Computer Science & Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

10 Oct 2022 05:49

Last Modified:

10 Oct 2022 05:49