Nearly-linear expected running time of ColorIsomorphic with WordReduction

Let the two inputs be transitive tuples of permutations in the symmetric group, with tuple length $d$, and choose the permutations uniformly at random. Nearly-linear running-time conjecture. The expected running time of the algorithm ${\sc ColorIsomorphic}$ with ${\sc WordReduction}$ improvement is nearly-linear in $n$ for fixed $d$. The paper establishes a worst-case bound of $O(n^2 \log d / \log n + dn\log n)$ for the simultaneous conjugacy problem in transitive tuples and reports experimental evidence for the conjecture; the expected near-linearity is not proved here.