A subquadratic algorithm for the simultaneous conjugacy problem

Thed $d$ ‐Simultaneous Conjugacy problem in the symmetric groupS n${S}_{n}$ asks whether there exists a permutationτ ∈ S n$\tau \in {S}_{n}$ such thatb j = τ − 1a j τ ${b}_{j}={\tau }^{-1}{a}_{j}\tau $ holds for allj = 1 , 2 , … , d $j=1,2,\ldots ,d$ , wherea 1 , a 2 , … , a d${a}_{1},{a}_{2},\ldots ,{a}_{d}$ andb 1 , b 2 , … , b d${b}_{1},{b}_{2},\ldots ,{b}_{d}$ are given sequences of permutations inS n${S}_{n}$ . The time complexity of existing algorithms for solving the problem isO ( d n 2 )$O(d{n}^{2})$ . We show that for a given positive integerd $d$ thed $d$ ‐Simultaneous Conjugacy problem inS n${S}_{n}$ can be solved ino ( n 2 )$o({n}^{2})$ time. Our algorithm solves a number of problems from various fields of mathematics and computer science.