## Stability and testability of permutations' equations

talk by Alexander Lubotzky

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.