Testability of relations between permutations

We initiate the study of property testing problems concerning relations between permutations. In such problems, the input is a tuple (σ 1, …, σ d ) of permutations on \{1, \ldots, n\}, and one wishes to determine whether this tuple satisfies a certain system of relations E, or is far from every tuple that satisfies E. If this computational problem can be solved by querying only a small number of entries of the given permutations, we say that E is testable. For example, when d=2 and E consists of the single relation \mathrm{XY}= \mathrm{YX}, this corresponds to testing whether σ 1 σ 2 =σ 2 σ 1, where σ 1 σ 2 and σ 2 σ 1 denote composition of permutations. We define a collection of graphs, naturally associated with the system E, that encodes all the information relevant to the testability of E. We then prove two theorems that provide criteria for testability and non-testability in terms of expansion properties of these graphs. By virtue of a deep connection with group theory, both theorems are applicable to wide classes of systems of relations. In addition, we formulate the well-studied group-theoretic notion of stability in permutations as a special case of the testa-bility notion above, interpret all previous works on stability as testability results, survey previous results on stability from a computational perspective, and describe many directions for future research on stability and testability. This is an extended abstract. The full version is available at https: //arxiv. org/abs/2011. 05234. All references beyond Sections I and II refer to the full version.

Authors

• Oren Becker
• Alexander Lubotzky
• Jonathan Mosheiff

Keywords

• Computer science
• Stability criteria
• Thermal stability
• Testing
• Class Of Systems
• Related Systems
• Group Theory
• Computational Perspective
• Relatedness
• Stability Of System
• Time Complexity
• Finite Set
• Flexible Model
• Examples Of Systems
• Input Size
• Word Length
• Testing Algorithm
• Directions For Further Research
• Survey Work
• Ball Of Radius
• Isomorphism Classes
• Edge Labels
• Query Efficiency
• Family Of Graphs
• Testability of relations between permutations
• Property testing
• Stability in permutations
• Graph expansion via group theory