Jonathan Mosheiff

This paper is a journal counterpart to [5], in which we initiate the study of property testing problems concerning a finite system of relations E between permutations, generalizing the study of stability in permutations. To every such system E, a group Γ = Γ_E is associated and the testability of E depends only on Γ (just like in Galois theory, where the solvability of a polynomial is determined by the solvability of the associated group). This leads to the notion of testable groups, and, more generally, Benjamini–Schramm rigid groups. The paper presents an ensemble of tools to check if a given group Γ is testable/BS-rigid or not.