Approximate polymorphisms of predicates
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915646135074816 |
|---|---|
| author | Alekseev, Yaroslav Filmus, Yuval |
| author_facet | Alekseev, Yaroslav Filmus, Yuval |
| contents | A generalized polymorphism of a predicate $P \subseteq \{0,1\}^m$ is a tuple of functions $f_1,\dots,f_m\colon \{0,1\}^n \to \{0,1\}$ satisfying the following property: If $x^{(1)},\dots,x^{(m)} \in \{0,1\}^n$ are such that $(x^{(1)}_i,\dots,x^{(m)}_i) \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 $μ$ on $P$), then $f_1,\dots,f_m$ are close to a generalized polymorphism of $P$ (with respect to the marginals of $μ$).
Our main result generalizes several results in the literature: linearity testing, quantitative Arrow theorems, approximate intersecting families, AND testing, and more generally $f$-testing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12155 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximate polymorphisms of predicates Alekseev, Yaroslav Filmus, Yuval Combinatorics Discrete Mathematics Probability A generalized polymorphism of a predicate $P \subseteq \{0,1\}^m$ is a tuple of functions $f_1,\dots,f_m\colon \{0,1\}^n \to \{0,1\}$ satisfying the following property: If $x^{(1)},\dots,x^{(m)} \in \{0,1\}^n$ are such that $(x^{(1)}_i,\dots,x^{(m)}_i) \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 $μ$ on $P$), then $f_1,\dots,f_m$ are close to a generalized polymorphism of $P$ (with respect to the marginals of $μ$). Our main result generalizes several results in the literature: linearity testing, quantitative Arrow theorems, approximate intersecting families, AND testing, and more generally $f$-testing. |
| title | Approximate polymorphisms of predicates |
| topic | Combinatorics Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2506.12155 |