Testability of relations between permutations

Add to your list(s) Download to your calendar using vCal

• Oren Becker (Cambridge)
• Thursday 03 March 2022, 14:30-15:30
• MR12.

If you have a question about this talk, please contact ibl10.

Let A and B be permutations in S_n, such that either () AB=BA, or () the pair (A,B) is far from every pair of permutations (A’,B’) satisfying A’B’=B’A’. Is there a probabilistic algorithm that distinguishes, with high probability of success, between Case () and Case () by reading only k entries of A and B, for k independent of n? In other words, is the equation XY=YX testable in permutations? What about other equations, such as XY^2=Y2 X or XY^2=Y3 X? What about simultaneous systems of equations? Problems of this sort belong to the field of Property Testing. I will explain how to approach them via group theory, bringing into play notions such as amenability, Kazhdan’s property (T), graph limits, hyperfiniteness and basis reduction theory.

Based on joint work with Alex Lubotzky and Jonathan Mosheiff.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.