## Select Seminar Series

All seminarsYou are here

- Home
- ›
- Studying at the Faculty
- ›
- Seminars ›
- Foundations of Computer Science Seminar

# 1

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 windowWe 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.