BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Testability of relations between permutations - O
ren Becker (Cambridge)
DTSTART;TZID=Europe/London:20220303T143000
DTEND;TZID=Europe/London:20220303T153000
UID:TALK170966AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/170966
DESCRIPTION:Let A and B be permutations in S_n\, such that eit
her (*) AB=BA\, or \n(**) the\npair (A\,B) is far
from every pair of permutations (A'\,B') satisfyin
g\nA'B'=B'A'. Is there a probabilistic algorithm t
hat distinguishes\, with high\nprobability of succ
ess\, between Case (*) and Case (**) by reading on
ly k\nentries of A and B\, for k independent of n?
In other words\, is the equation\nXY=YX testable
in permutations? What about other equations\, such
as\nXY^2=Y^2 X or XY^2=Y^3 X? What about simultan
eous systems of equations?\nProblems of this sort
belong to the field of Property Testing. I will\ne
xplain how to approach them via group theory\, bri
nging into play notions\nsuch as amenability\, Kaz
hdan's property (T)\, graph limits\,\nhyperfiniten
ess and basis reduction theory.\n\nBased on joint
work with Alex Lubotzky and Jonathan Mosheiff.\n
LOCATION:MR12
CONTACT:
END:VEVENT
END:VCALENDAR