You are here


MondayAug 15, 202211:15
Foundations of Computer Science SeminarRoom 155
Speaker:Alexander LubotzkyTitle:Stability and testability of permutations' equationsAbstract:opens in new windowin html    pdfopens in new window
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 which 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.