We initiate the study of property testing problems concerning relations between permutations. In such problems, the input is a tuple $(sigma_1,dotsc,sigma_d)$ of permutations on ${1,dotsc,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 $mathsf{XY=YX}$, this corresponds to testing whether $sigma_1sigma_2=sigma_2sigma_1$, where $sigma_1sigma_2$ and $sigma_2sigma_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 testability 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.
تحميل البحث