arXiv preprint ·
Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study isomorphism decision and basis construction for finite Abelian groups of known order $n$. 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 $\tilde O(n^{1/4})$ group additions and runs in $\tilde O(n^{1/4})$ time. This improves the $\tilde O(\sqrt n)$ upper bound of Chen and Fu and matches Bshouty $Ω(n^{1/4})$ lower bound up to polylogarithmic factors. We also prove that finding a basis with success probability at least $2/3$ requires $Ω(\sqrt n)$ group additions in the worst case. This matches the $\tilde O(\sqrt n)$ 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 $\tildeΘ(n^{1/4})$ and $\tildeΘ(\sqrt n)$, respectivel
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Clifford Invariants and Three-Copy Quantum Tests
A Cohomological Characterization of the Clifford Hierarchy
Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension
Amenable groups with nearly exponential sofic profile, and quantum channels that need nearly linear memory
The Symmetry of Differential Neural Tangent Kernel under the Orthogonal Group
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.