Linear time algorithm for the conjugacy problem in the first Grigorchuk group

Mitra Modi, Mathew Seedhom, Alexander Ushakov

We prove that the conjugacy problem in the first Grigorchuck group $\Gamma$ can be solved in linear time. Furthermore, the problem to decide if a list of elements $w_1,\dots ,w_k\in \Gamma$ c…