University of Cambridge > Talks.cam > Combinatorics Seminar > Testability of relations between permutations

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Testability of relations between permutations

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 .

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Cripps Court Auditorium, 1-3 Chesterton Road IOP East Anglia Branch Applied Physics Seminars Cambridge Centre for Brain Repair

Other talks

Group Work Think Before you Speak: Next Gen LLMs with Global Reasoning and External Memory Title to be confirmed Title TBC TBC Title to be confirmed: CMS
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity