Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups
In the authors' words
We study isomorphism decision and basis construction for finite Abelian groups of known order . We measure complexity by the number of additions performed in the groups and by the total running time. We give a randomized isomorphism decision algorithm that performs group additions and runs in time. This improves the upper bound of Chen and Fu and matches Bshouty lower bound up to polylogarithmic factors. We also prove that finding a basis with success probability at least requires group additions in the worst case. This matches the upper bound of Chen and Fu up to polylogarithmic factors. These results separate isomorphism decision from basis construction in finite Abelian groups: their optimal worst-case complexities are and , respectivel
Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.