On the complexity of isomorphism problems for tensors, groups, and polynomials I: tensor isomorphism-completeness
We study the complexity of isomorphism problems for tensors, groups, and polynomials.
These problems have been studied in multivariate cryptography, machine learning, quantum …
These problems have been studied in multivariate cryptography, machine learning, quantum …
Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝
X Sun - Proceedings of the 55th Annual ACM Symposium on …, 2023 - dl.acm.org
The group isomorphism problem determines whether two groups, given by their Cayley
tables, are isomorphic. For groups with order n, an algorithm with n (log n+ O (1)) running …
tables, are isomorphic. For groups with order n, an algorithm with n (log n+ O (1)) running …
On p-Group Isomorphism: Search-to-Decision, Counting-to-Decision, and Nilpotency Class Reductions via Tensors
JA Grochow, Y Qiao - ACM Transactions on Computation Theory, 2024 - dl.acm.org
In this article, we study some classical complexity-theoretic questions regarding Group
Isomorphism (GpI). We focus on p-groups (groups of prime power order) with odd p, which …
Isomorphism (GpI). We focus on p-groups (groups of prime power order) with odd p, which …
Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions
JA Grochow, Y Qiao - arXiv preprint arXiv:1907.00309, 2019 - arxiv.org
In this paper we consider the problems of testing isomorphism of tensors, $ p $-groups,
cubic forms, algebras, and more, which arise from a variety of areas, including machine …
cubic forms, algebras, and more, which arise from a variety of areas, including machine …
On the Weisfeiler-Leman dimension of finite groups
J Brachter, P Schweitzer - Proceedings of the 35th Annual ACM/IEEE …, 2020 - dl.acm.org
In comparison to graphs, combinatorial methods for the isomorphism problem of finite
groups are less developed than algebraic ones. To be able to investigate the descriptive …
groups are less developed than algebraic ones. To be able to investigate the descriptive …
A systematic study of isomorphism invariants of finite groups via the Weisfeiler-Leman dimension
J Brachter, P Schweitzer - arXiv preprint arXiv:2111.11908, 2021 - arxiv.org
We investigate the relationship between various isomorphism invariants for finite groups.
Specifically, we use the Weisfeiler-Leman dimension (WL) to characterize, compare and …
Specifically, we use the Weisfeiler-Leman dimension (WL) to characterize, compare and …
On the Baer–Lovász–Tutte construction of groups from graphs: Isomorphism types and homomorphism notions
Let p be an odd prime. From a simple undirected graph G, through the classical procedures
of Baer (1938), Tutte (1947) and Lovász (1989), there is a p-group PG of class 2 and …
of Baer (1938), Tutte (1947) and Lovász (1989), there is a p-group PG of class 2 and …
Improved algorithms for alternating matrix space isometry: From theory to practice
Motivated by testing isomorphism of p-groups, we study the alternating matrix space
isometry problem (AltMatSpIso), which asks to decide whether two m-dimensional …
isometry problem (AltMatSpIso), which asks to decide whether two m-dimensional …
Count-Free Weisfeiler--Leman and Group Isomorphism
NA Collins, M Levet - arXiv preprint arXiv:2212.11247, 2022 - arxiv.org
We investigate the power of counting in\textsc {Group Isomorphism}. We first leverage the
count-free variant of the Weisfeiler--Leman Version I algorithm for groups (Brachter & …
count-free variant of the Weisfeiler--Leman Version I algorithm for groups (Brachter & …
On the Parallel Complexity of Group Isomorphism via Weisfeiler–Leman
JA Grochow, M Levet - International Symposium on Fundamentals of …, 2023 - Springer
In this paper, we show that the constant-dimensional Weisfeiler–Leman algorithm for groups
(Brachter & Schweitzer, LICS 2020) can be fruitfully used to improve parallel complexity …
(Brachter & Schweitzer, LICS 2020) can be fruitfully used to improve parallel complexity …