Stability and Testability

In this talk we survey the recent connection (a joint work with Becker and Lubotzky) between certain group theoretic notions related to stability, and a novel class of problems from the realm of property testing. Consider the computational problem where we are given a tuple of permutations in $Sym(n)$, and wish to determine whether these permutations satisfy a certain system of equations $E$. We say that $E$ is testable if there is an algorithm (called a tester) that queries only a constant number of entries of the given permutations, and probabilistically distinguishes between the case where the permutations satisfy $E$, and the case in which they are epsilon-far from any tuple of permutations satisfying $E$. Note that in our definition of this problem we depart from the more classical setting of property testing, where the object to be tested is either a function or a graph. We observe an intriguing connection between the group presented by $E$, which we denote $G$, and the above computational problem. It turns out that $G$ is stable if and only if a certain natural algorithm is a tester for $E$. Thus, established results about the stability of certain groups yield testers for corresponding systems of equations. Further exploring this connection, we discover that the testability of $E$ can be fully characterized in terms of the group $G$. Studying this characterization yields both positive and negative results. For example, amenability of $G$ implies that $E$ is testable. On the other hand, if $G$ has property (T) and finite quotients of unbounded cardinality, then $E$ is not testable. We conclude by presenting some natural open questions motivated by this work.