CS Paper Radar

Faster Isomorphism for Groups of Class 2

Xiaorui Sun

cs.DS ·submitted 2026-11-04 04:13 UTC · v1

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.

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.88
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

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.69
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

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

cs.DS math.GR ·2026-10-06 ·Nader H. Bshouty
theory similarity 0.69
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

0.11

Word Length and Diameter in Permutation Groups

cs.CC math.GR ·2026-09-22 ·Markus Lohrey, Alexander Thumm
similarity 0.65
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

FPT Isomorphism Test for $F$-Free Tournaments

cs.DS cs.DM ·2026-09-21 ·Daniel Neuen
similarity 0.54
Abstract · 17 pages

We show that isomorphism of $F$-free tournaments can be solved in FPT time $f(k) \cdot n^{O(1)}$, where $k$ denotes the size of $F$, and $n$ denotes the size of the input tournaments. Our result extends on a previous FPT isomorphism test for tournaments of bounded twin-width [Grohe, Neuen 2024], as well as XP isomorphism tests parameterized by the VC dimension or the chromatic number [Raßmann, Schweitzer 2026]. It also implies that every non-trivial hereditary class of tournaments admits a polynomial-time isomorphism test. Our algorithm builds on a novel combination of spectral, geometric, combinatorial and group-theoretic tools.

0.11

Constructive Arithmetic Regularity for Abelian Groups

cs.DS ·2026-10-19 ·Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manmatha Roy
similarity 0.54
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

Boxicity of Power Graphs of Finite Nilpotent Groups

cs.DM math.COmath.GR ·2026-11-04 ·L. Sunil Chandran, Jinia Ghosh, Suraj Kumar Sahoo
theory similarity 0.54
Abstract · 28 pages

The \textit{boxicity} of an undirected graph $Γ$, denoted as $\operatorname{box}(Γ)$, is the smallest non-negative integer $d$ such that $Γ$ can be represented as the intersection graph of axis-parallel rectangular boxes in $\mathbb{R}^d$. The \emph{power graph} of a group $G$, denoted as $\operatorname{Pow}(G)$, is an undirected graph whose vertex set is the group itself, with two elements being adjacent if one is a power of the other. We determine the exact boxicity of power graphs of finite nilpotent groups. For a cyclic group of order $n=\prod_{i=1}^{r}p_i^{e_i}>1$, where the $p_i$ are distinct primes, we prove that its power graph has boxicity $\sum_{i=1}^{r}e_i-\max_i e_i$. For a finite nilpotent group $G$, let the number of noncyclic odd Sylow subgroups be denoted by $t(G)$. If $G$ has odd order or if $G$ has a cyclic Sylow $2$-subgroup, then $\operatorname{box}(\operatorname{Pow}(G))=\operatorname{box}(\operatorname{Pow}(\mathbb{Z}_{\operatorname{exp}(G)}))+t(G)$, where $\operatorname{exp}(G)$ denotes the \emph{exponent} of a group $G$. When the Sylow $2$-subgroup is noncyclic, and the odd part is nontrivial, the boxicity equals this value or one more, and we characterise precisely when each of these values is attained. The boxicity of power graphs of arbitrary finite groups and the exact boxicity of the comparability graph of the Boolean lattice were posed as open questions in Discrete Mathematics, 349(7):115017, 2026. As a consequence of our results, we answer the latter question completely and the former question partially, by computing the exact boxicity of the power graphs of nilpotent groups.

0.27

Coset Lifted Product Codes: Constructing Quantum LDPC Codes from Non-Normal Subgroup Actions

cs.IT quant-ph ·2026-10-08 ·Rajendra Prasad Rajpurohit, V. Lalitha, Shayan Srinivasa Garani
similarity 0.53
Abstract

We introduce coset lifted product (CLP) codes, a family of quantum LDPC codes that combine the protograph structure of lifted product codes with the coset action of Aydin, Tamo, and Barg \cite{AydinTamoBarg2026}. Given a finite group $G$, a subgroup $H \le G$ that need not be normal, a protograph $A$ over $\mathbb F_2[G]$, and a protograph $B$ over $\mathbb F_2[N_G(H)]$, the two protographs act on the cosets $G/H$ from the left and from the right to produce quantum CSS codes. Further, for groups of odd order, we give an explicit formula for the dimension as a sum over the irreducible representations $ρ$ of $G$ of hypergraph product dimensions. A search over $14,843$ pairs $(G,H)$ with $H$ restricted to be non-normal and $120 \le n \le 400$ yields certified codes that exceed the best published value of $Q=kd^2/n$ at check weights $6,7$ and $9$, i.e., we obtain $[[360,20,20]]$ at $w=6$, a $[[360,24,20]]$ code at $w=7$, and codes $[[252,16,18]]$ and $[[288,16,20]]$ at $w=9$. Our search also produce high-distance codes with parameters $[[168,10,14]], [[240,8,20]]$ at $w=6$ and $[[216,8,18]]$ at $w=7$.

0.18