CS Paper Radar

Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups

Nader H. Bshouty

cs.DS math.GR ·submitted 2026-10-06 12:52 UTC · v1
theory

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

Closest papers

Nearest neighbours by meaning across the whole index.

Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2

cs.DS math.GR ·2026-10-01 ·Joshua A. Grochow, Gábor Ivanyos, Youming Qiao, Xiaorui Sun
top venue similarity 0.69
Abstract · 55 pages, accepted to FOCS 2026

The finite group isomorphism problem asks whether two finite groups of order $N$ are isomorphic. The first algorithm, attributed to Tarjan (see Miller, STOC '78), runs in time $N^{\log N + O(1)}$. Despite intensive study, the current best known algorithm has a running time of $N^{(1 / 4 + o(1))\log N}$ (Rosenbaum, '13). $p$-groups of class $2$ have been recognized as the major bottleneck for faster group isomorphism. Recent progress has led to $N^{o(\log N)}$-time algorithms for $p$-groups of class $2$ where $p$ is odd (Sun, STOC '23; Ivanyos--Mendoza--Qiao--Sun--Zhang, FOCS '24; Grochow--Qiao--Stange--Sun, STOC '25). However, the case of $p=2$, which represents the majority of $p$-groups of class 2 assuming a well-known conjecture in group enumeration, remained elusive, with essentially no progress until now. In this paper, we present an algorithm for testing the isomorphism of two 2-groups of Frattini class 2 of order $N$ in time $N^{O((\log N)^{1/2})}$. To our knowledge, this is the first $N^{o(\log N)}$-time isomorphism algorithm for a class of $2$-groups that constitutes logarithmically almost all $2$-groups, in the sense that $\lim_{N \to \infty} \frac{\log(\text{\# 2-groups of Frattini class 2 and order } \leq N)}{\log(\text{\# 2-groups of order} \leq N)} = 1$. As our main tool, we present the first non-trivial algorithms for the quadratic form space/tuple isometry problems over $\mathbb{F}_2$. These algorithms rely on combinations of combinatorial and algebraic ideas, including finite matrix group algorithms developed by Luks (FOCS '92). As far as we know, this is the first time that matrix group algorithms are used to make progress on the worst-case complexity of $p$-group isomorphism.

0.65

Faster Isomorphism for Groups of Class 2

cs.DS ·2026-11-04 ·Xiaorui Sun
similarity 0.69
Abstract

The finite-group isomorphism problem asks whether two groups, given by their Cayley tables, are isomorphic. Despite decades of study, obtaining an $N^{o(\log N)}$-time algorithm for general groups of order $N$ remains a major open challenge. Groups of nilpotency class $2$ have long been a central obstacle to achieving this goal. Recent breakthroughs have established $N^{o(\log N)}$-time algorithms for $p$-groups of class $2$ with odd $p$ (Sun, STOC '23; Ivanyos-Mendoza-Qiao-Sun-Zhang, FOCS '24; Grochow-Qiao-Stange-Sun, STOC '25) and for groups of Frattini class $2$ (Grochow-Ivanyos-Qiao-Sun, FOCS '26). However, the problem remained open for general groups of class $2$. In this paper, we present an algorithm for testing isomorphism of groups of class $2$, with running time $N^{O((\log N)^{25/26} \log \log N)}$. Our algorithm combines a tensor-based restriction of the search space, an encoding of group relations by alternating matrix tuples, and an orbit computation to recover the remaining central power information.

0.06

Algorithms for Finite Group Epimorphism Testing

cs.DS cs.CCmath.GR ·2026-09-07 ·Joshua A. Grochow, Pranjal Srivastava, Dhara Thakkar
top venue similarity 0.64
Abstract · 19 pages, A preliminary version of this article appeared in the proceedings of the 53rd EATCS International Colloquium on Automata, Language…

The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about its complexity for structured classes of finite groups. In this paper, we study the computational complexity of GpEpi for several well-studied classes of finite groups. Our main results are polynomial-time epimorphism tests for several classes of groups for which polynomial-time isomorphism testing was previously known: Groups with Abelian normal Hall subgroups with cyclic complement; Groups with (product of) elementary Abelian normal Hall subgroup with elementary Abelian complement; and Groups with some constraints on their Abelian chief factors.

0.63

Word Length and Diameter in Permutation Groups

cs.CC math.GR ·2026-09-22 ·Markus Lohrey, Alexander Thumm
similarity 0.64
Abstract

In the binary diameter problem, the input consists of explicitly given permutations generating a finite group $G$ and a binary-encoded number $k$, and the question is whether every element of $G$ is a product of at most $k$ of the given generators. In the binary length problem, the input additionally contains a permutation $g \in G$, and the question is whether $g$ is such a product. We show that the binary diameter problem is PSPACE-complete, thereby confirming a conjecture of Lohrey and Rosowski (2023). Moreover, we show that PSPACE-hardness already holds for solvable groups of derived length at most 3, whereas the problem is $Π_2^{\mathrm{P}}$-complete for 2-step nilpotent groups. For the binary length problem, we establish a sharp complexity threshold: the problem is NP-complete for 2-step nilpotent groups, which extends a result of Lohrey and Rosowski for abelian groups, and PSPACE-complete for groups that are simultaneously 3-step nilpotent and metabelian, which strengthens the main result of Jerrum (1985). Finally, we show that the unary diameter problem, where $k$ is encoded in unary, is $Π_2^{\mathrm{P}}$-complete for generating sets of the full symmetric group, confirming another conjecture of Lohrey and Rosowski.

0.28

Constructive Arithmetic Regularity for Abelian Groups

cs.DS ·2026-10-19 ·Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manmatha Roy
similarity 0.62
Abstract

The arithmetic regularity lemma of Green is a fundamental tool in additive combinatorics, providing a decomposition of arbitrary subsets of finite Abelian groups into pseudorandom pieces with respect to Fourier analysis. Over the years, it has found numerous applications in combinatorics, property testing, and theoretical computer science. However, Green's proof is existential, and many algorithmic applications require an efficient procedure for constructing the underlying regular decomposition. De, Nadimpalli, and Servedio (SODA 2022) developed a query-efficient constructive regularity framework over $\mathbb{F}_2^n$ and explicitly raised the problem of extending their dimension-independent sumset-estimation algorithm to other finite Abelian groups. In this work, we resolve this question for finite Abelian groups of constant torsion. We develop the first constructive version of Green's {\em Arithmetic Regularity Lemma} in this general setting. Given oracle access to a subset of the group, our algorithm computes an implicit description of a regular decomposition together with an oracle representation of a structured subset satisfying the guarantees of Green's lemma. The algorithm runs in time and query complexity polynomial in the regularity parameters and the tower bound, while remaining independent of the size of the ambient group. As applications, we obtain efficient algorithms for removing linear configurations and approximately counting linear images, including weighted sumsets and suitable matrix systems of Cauchy--Schwarz complexity one, over finite Abelian groups of constant torsion. Our results provide a unified algorithmic framework extending dimension-independent constructive arithmetic regularity and its applications beyond $\mathbb{F}_2^n$.

0.27

On the sample complexity of the generalized hidden shift problem over arbitrary finite groups

cs.CC quant-phmath.GR ·2026-09-05 ·Juntai Zhou
similarity 0.61
Abstract

We formulate the generalized hidden shift problem over arbitrary finite groups and obtain upper and lower bounds for the sample complexity in terms of group theoretic data.

0.43

Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices

cs.CR math.COmath.MG ·2026-10-11 ·Thijs Laarhoven
theory similarity 0.60
Abstract · 27 pages, 4 figures, 2 tables

To bridge the gap between worst-case and heuristic analyses of lattice enumeration, we study the sizes of (unpruned) enumeration trees on $n$-dimensional Haar-random lattices. Writing $n^{cn+o(n)}$ for the tree size at the shortest vector radius, we investigate the asymptotic scaling of $c$, and which bases minimize it. For quasi-HKZ bases, we rigorously analyze the random-lattice HKZ geometry and establish $c=1/(2e)\approx 0.1839$. This matches the worst-case enumeration exponent of Hanrot-Stehlé and confirms earlier predictions for the geometry of HKZ bases on random lattices. Searching beyond quasi-HKZ bases, we prove that with high probability, the minimum achievable tree size exponent $c$ over all bases of a random lattice satisfies: \begin{align} 0.1464 \approx \frac{2-\sqrt{2}}{4}\leq c<0.1474. \end{align} For the lower bound, we use Kim's mean-value formula for nested chains of primitive sublattices to rule out bases with small prefix determinants. This strengthens the earlier Rankin-based heuristic lower bound exponent $c \geq 1/8$, discussed by Nguyen and Hanrot-Stehlé, and rules out the existence of random-lattice bases with trees as small as predicted by the geometric series assumption. For the upper bound, we show that with high probability a dense primitive half-rank sublattice exists with determinant at most $n^{n/8 + o(n)}$. Combining dual HKZ on this sublattice with HKZ on its quotient gives a basis with $c \leq 1/(4\sqrt{e}) \approx 0.1516$. Recursively splitting each half lowers the upper bound below $0.1474$, and under a natural heuristic assumption we prove that the lower bound is tight. Combined with the collision search of Feng-Gao-Liu, our two-block construction gives a polynomial-space algorithm solving the closest vector problem with preprocessing (CVPP) on random lattices in query time $n^{0.0892 n + o(n)}$ for arbitrary targets.

0.52

Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security

cs.CR math.CO ·2026-09-28 ·Ritam Bhaumik, Chun Guo, Xiaoning Guo, Ashwin Jha
hot direction similarity 0.58
Abstract

We study classical and quantum indistinguishability of sums of independent random permutations and related transformations from permutations to functions. Let $G$ be a finite abelian group of order $N$, and let $π^k_+(x)=π_1(x)+\cdots+π_k(x)$ for $k\geq2$ independent uniform random permutations of $G$. We give a unified Fourier analytic treatment in which the construction is represented by its probability density and a distinguisher by its acceptance function, with the classical and quantum query models imposing different restrictions on the Fourier support of the latter. Classically, we obtain the bound $O_k(q/N^{k-1/2})$ for every $q<N$, and refine it below the birthday threshold to $O_k(q^2/N^k)$. In the quantum model, a simulation argument gives $O_k(N^{-(k-3/2)})$ for $q\leq(N-1)/2$, while Fourier interpolation gives concrete finite bounds up to $q\leq4N/15$ and the query-dependent bounds $O\left(\min\left\{N^{-1/2},q^3/N^2 + 1/N\right\}\right)$ and $O_k\left(\min\left\{q^3/N^k,N^{-(k-3/2)}\right\}\right)$, for $k=2$ and $k \geq 3$, respectively, throughout $1\leq q\leq(N-1)/2$. For $q = 1$, the first bound sharpens to $O(N^{-2})$. Over $G=\mathbb F_2^n$, a one-query Fourier attack matches the order of our one-query bound, while an $N/2$-query parity attack with advantage $1/2$ shows that our bounds reach the constant-advantage query threshold. We further study two variants of sum of permutations over binary vector spaces. First, we allow arbitrary surjective linear postprocessing, which includes truncation, and obtain classical and quantum bounds that retain the output-size dependence. Second, we analyse Dinur's variable-output single-permutation construction, $\mathsf{LXoP}$, for every fixed output width, and derive its classical and quantum security bounds; for one- and two-block outputs, we give concrete quantum security bounds.

0.38