BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Testability of relations between permutations  - Oren Becker (Camb
 ridge) 
DTSTART:20220303T143000Z
DTEND:20220303T153000Z
UID:TALK170966@talks.cam.ac.uk
CONTACT:103978
DESCRIPTION:Let A and B be permutations in S_n\, such that either (*) AB=B
 A\, or \n(**) the\npair (A\,B) is far from every pair of permutations (A'\
 ,B') satisfying\nA'B'=B'A'. Is there a probabilistic algorithm that distin
 guishes\, with high\nprobability of success\, between Case (*) and Case (*
 *) by reading only k\nentries of A and B\, for k independent of n? In othe
 r words\, is the equation\nXY=YX testable in permutations? What about othe
 r equations\, such as\nXY^2=Y^2 X or XY^2=Y^3 X? What about simultaneous s
 ystems of equations?\nProblems of this sort belong to the field of Propert
 y Testing. I will\nexplain how to approach them via group theory\, bringin
 g into play notions\nsuch as amenability\, Kazhdan's property (T)\, graph 
 limits\,\nhyperfiniteness and basis reduction theory.\n\nBased on joint wo
 rk with Alex Lubotzky and Jonathan Mosheiff.\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR