Talk
What is... group stability?
Talk by Francesco Fournier Facio
Date: 27.04.21 Time: 16.15 - 18.30 Room:
Consider the following algorithmic question: given two permutations of degree n, find an algorithm that checks whether they commute. It is easy to find a linear-time algorithm that does this, but when n is very large, this may take too long. So let us ask instead: is there a constant-time algorithm that accepts commuting permutations, and rejects permutations which are far from any pair of commuting ones, with high probability?
This problem belongs to the realm of property-testing, a very active field of research in computer science. But surprisingly, the first answer comes from group theory. Starting from this problem, we will introduce the notion of stability in permutations of a group, which was introduced in 2014 by Arzhantseva and Paunescu. We will compare this with other more classical stability problems, and see that it has connections to many different fields of mathematics.
Time permitting, we will explain why the framework of stability provides a promising strategy in the quest for a non-sofic group.