University of Cambridge > > Combinatorics Seminar > Testability of relations between permutations

Testability of relations between permutations

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

  • UserOren Becker (Cambridge)
  • ClockThursday 03 March 2022, 14:30-15:30
  • HouseMR12.

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 XY2=Y2 X or XY2=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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2022, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity