The simultaneous conjugacy problem

Let S_n be the symmetric group on n letters. Given two r-tuples (a_1,a_2,…,a_r) and (b_1,b_2,…,b_r) of permutations of S_n the decision r-simultaneous conjugacy problem asks whether there is a permutation \tau in S_n which simultaneously conjugates these two tuples, that is, whether the following system of equations b_j = \tau^{-1}a_j\tau, j=1,2,…,r, over S_n has a solution. The search version of this problem is defined in the obvious manner, and is referred to as the search simultaneous conjugacy problem.

The solution of the simultaneous conjugacy problem has great potential for a variety of applications in different fields of mathematics and computer science such as automata theory, permutation groups, maps on surfaces, graph theory, representation theory, and cryptography. For example, in the language of deterministic finite automata the decision simultaneous conjugacy problem  is precisely the semiautomata isomorphism problem. The question whether two oriented maps on a closed surface are isomorphic translates to the special case of the decision simultaneous conjugacy problem for r = 2. Also, the decision problem interpreted in terms of permutation matrices is equivalent to a special case of asking whether two group representations are equivalent. An important variant of the conjugacy problem occurs when asking for all solution where a_j = b_j for all indices j; in this case we ask for the centralizer of a given set of permutations. In particular, this is encountered in finding the automorphism groups of embedded graphs on surfaces. Further, in the theory of covering graphs the question whether two covering projections are equivalent translates to the decision version of the conjugacy problem. Last but not least, the simultaneous conjugacy problem can be naturally generalised to arbitrary groups. For instance, in braid groups the search problem plays an important role in studying braid cryptographic protocols.

The best-known deterministic algorithm which solves the search version (and hence the decision version) has the \mathcal{O}(rn^2) time complexity. In addition, there are no lower bounds in the literature for the decision/search simultaneous conjugacy problem, except the trivial linear bound \mathcal{O}(rn). In the talk we present some new results which reduce the gap between the upper and lower bound. 

Joint work with Andrej Brodnik and Aleksander Malnič.