Stability and testability - a computational perspective

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)Sym(n), and wish to determine whether these permutations satisfy a certain system of equations EE. We say that EE 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 EE, and the case in which they are epsilon-far from any tuple of permutations satisfying EE. 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 EE, which we denote GG, and the above computational problem. It turns out that GG is stable if and only if a certain natural algorithm is a tester for EE. 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 EE can be fully characterized in terms of the group GG. Studying this characterization yields both positive and negative results. For example, amenability of GG implies that EE is testable. On the other hand, if GG has property (T) and finite quotients of unbounded cardinality, then EE is not testable. We conclude by presenting some natural open questions motivated by this work.