2025/06/13 by Ya. I. Alekseev, Yuval Filmus, Alekseev, Yaroslav +1
Computer Science · Decision Sciences · Mathematics · #Advanced Algebra and Logic #Advanced Topology and Set Theory #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Fuzzy and Soft Set Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2506.12155
openalex publication_date 2025/06/13 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28
A generalized polymorphism of a predicate P ⊆ \0,1\m is a tuple of functions f1,…,fm\colon \0,1\n → \0,1\ satisfying the following property: If x(1),…,x(m) ∈ \0,1\n are such that (x(1)i,…,x(m)i) ∈ P for all i, then also (f1(x(1)),…,fm(x(m))) ∈ P. We show that if f1,…,fm satisfy this property for most x(1),…,x(m) (as measured with respect to an arbitrary full support distribution μ on P), then f1,…,fm 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.