For a fixed word equation such as XY=YX, or even a fixed system of such equations, given oracle access to permutations $A,B:[n]\to[n]$, they consider the question of testing whether $A$ and $B$ satisfy the equation(s). Actually, they seek non-adaptive proximity oblivious testers (POTs); that is, one-sided error testers that reject objects that at distance $\delta$ from the property with probability at least $F(\delta)$, where $F$ is a fixed function. Furthermore, they are particularly interested in the case that the equations themselves provide a robust characterization of the property (i.e., testing is performed by checking whether the equation hold at a random assignment), and in this case they call the equations stable.
It turns out that even in the case of a single equation, characterizing the cases that have a non-adaptive POT (resp., the cases that constitute robust characterization) is extremely challenging. While the equation XY=YX is a robust characterization, the equation XYY=YYX has no POT. I find this demonstration of the fragility of the question of being a robust characterization (resp., having a POT) extremely fascinating.
We study a new direction of research in property testing: Permutation equations. Let A and B be two permutations in Sym(n) that "almost commute"; are they a small deformation of permutations that truly commute? More generally, if R is a system of word-equations in variables X=x_1,....,x_d and A_1,....,A_d are permutations that are almost a solution; are they near true solutions?
It turns out that the answer to this question depends only on the group presented by the generators X and relations R. This leads to the notions of "stable groups" and "testable groups" and calls for some group theoretic methods for answering these questions. We will present a few results and methods which were developed in recent years to check whether a group is stable/testable (e.g., using IRS's= invariant random subgroups). We will also describe the connection of this subject with locally testable codes as well as with the long-standing problem of whether every group is sofic.