Approximate polymorphisms
Pages 195 - 202
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.
References
[1]
Kenneth J. Arrow. 1950. A Difficulty in the Concept of Social Welfare. Journal of Political Economy, 58, 4 (1950), 328–346. https://doi.org/10.1086/256963 arxiv:https://doi.org/10.1086/256963.
[2]
Libor Barto, Andrei Krokhin, and Ross Willard. 2017. Polymorphisms, and how to use them. In Dagstuhl Follow-Ups. 7.
[3]
Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos Kiwi, and Madhu Sudan. 1996. Linearity testing in characteristic two. IEEE Trans. Inform. Theory, 42, 6, part 1 (1996), 1781–1795. issn:0018-9448 https://doi.org/10.1109/18.556674 Codes and complexity
[4]
Manuel Blum, Michael Luby, and Ronitt Rubinfeld. 1990. Self-Testing/Correcting with Applications to Numerical Problems. In STOC. 73–83.
[5]
Elad Dokow and Ron Holzman. 2009. Aggregation of binary evaluations for truth-functional agendas. Soc. Choice Welf., 32, 2 (2009), 221–241. issn:0176-1714 https://doi.org/10.1007/s00355-008-0320-1
[6]
Elad Dokow and Ron Holzman. 2010. Aggregation of non-binary evaluations. Adv. in Appl. Math., 45, 4 (2010), 487–504. issn:0196-8858 https://doi.org/10.1016/j.aam.2010.02.005
[7]
Yuval Filmus, Noam Lifshitz, Dor Minzer, and Elchanan Mossel. 2020. AND testing and robust judgement aggregation. In 52nd ACM Symposium on Theory of Computing (STOC’20).
[8]
Ehud Friedgut and Oded Regev. 2018. Kneser graphs are like Swiss cheese. Discrete Anal., Paper No. 2, 18. https://doi.org/10.19086/da
[9]
Johan Håstad. 2001. Some optimal inapproximability results. J. ACM, 48, 4 (2001), 798–859. https://doi.org/10.1145/502090.502098
[10]
Chris Jones. 2016. A Noisy-Influence Regularity Lemma for Boolean Functions. CoRR, abs/1610.06950 (2016), arxiv:1610.06950. arxiv:1610.06950
[11]
Gil Kalai. 2002. A Fourier-theoretic perspective on the Condorcet paradox and Arrow’s theorem. Adv. in Appl. Math., 29, 3 (2002), 412–426. issn:0196-8858 https://doi.org/10.1016/S0196-8858(02)00023-4
[12]
Nathan Keller. 2012. A tight quantitative version of Arrow’s impossibility theorem. J. Eur. Math. Soc. (JEMS), 14, 5 (2012), 1331–1355. issn:1435-9855 https://doi.org/10.4171/JEMS/334
[13]
Elchanan Mossel. 2010. Gaussian bounds for noise correlation of functions. Geom. Funct. Anal., 19, 6 (2010), 1713–1756. issn:1016-443X https://doi.org/10.1007/s00039-010-0047-x
[14]
Elchanan Mossel. 2012. A quantitative Arrow theorem. Probab. Theory Related Fields, 154, 1-2 (2012), 49–88. issn:0178-8051 https://doi.org/10.1007/s00440-011-0362-7
[15]
Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. 2010. Noise stability of functions with low influences: Invariance and optimality. Annals of Mathematics, 171, 1 (2010), 295–341.
[16]
Joe Neeman. 2014. A multidimensional version of noise stability. Electron. Commun. Probab., 19 (2014), no. 72, 10. https://doi.org/10.1214/ECP.v19-3005
[17]
Ilan Nehama. 2013. Approximately classic judgement aggregation. Ann. Math. Artif. Intell., 68, 1-3 (2013), 91–134. issn:1012-2443 https://doi.org/10.1007/s10472-013-9358-6
[18]
Michal Parnas, Dana Ron, and Alex Samorodnitsky. 2002. Testing basic Boolean formulae. SIAM J. Disc. Math., 16, 1 (2002), 20–46.
[19]
Mario Szegedy and Yixin Xu. 2015. Impossibility Theorems and the Universal Algebraic Toolkit. Unpublished note.
[20]
Robert Wilson. 1972. Social choice theory without the Pareto principle. J. Econom. Theory, 5, 3 (1972), 478–486. issn:0022-0531 https://doi.org/10.1016/0022-0531(72)90051-8
Index Terms
- Approximate polymorphisms
Recommendations
On the Complexity of Symmetric vs. Functional PCSPs
The complexity of the promise constraint satisfaction problem \(\operatorname{(PCSP)}(\mathbf{A},\mathbf{B})\) is largely unknown, even for symmetric \(\mathbf{A}\) and \(\mathbf{B}\) , except for the case when \(\mathbf{A}\) and \(\mathbf{B}\) ...
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its vertices such that every hyperedge intersects all $r$ color classes. Given as input such a hypergraph, finding a $r$-rainbow coloring of it is NP-hard for all $...
Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)
For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby, and Rubinfeld [J. Comput. System ...
Comments
Information & Contributors
Information
Published In
June 2022
1698 pages
Copyright © 2022 Owner/Author.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 10 June 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
STOC '22
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Upcoming Conference
STOC '25
- Sponsor:
- sigact
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 255Total Downloads
- Downloads (Last 12 months)89
- Downloads (Last 6 weeks)12
Reflects downloads up to 25 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in