On the parallel complexity of group isomorphism via Weisfeiler-Leman (Q6885372)

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

On the parallel complexity of group isomorphism via Weisfeiler-Leman

scientific article; zbMATH DE number 8135744

Language	Label	Description	Also known as
default for all languages	No label defined
English	On the parallel complexity of group isomorphism via Weisfeiler-Leman	scientific article; zbMATH DE number 8135744

Statements

instance of

scholarly article

0 references

title

On the parallel complexity of group isomorphism via Weisfeiler-Leman (English)

0 references

0 references

0 references

Journal of Computer and System Sciences

0 references

publication date

11 December 2025

0 references

zbMATH Keywords

group isomorphism

0 references

graph isomorphism

0 references

Weisfeiler-Leman algorithm

0 references

descriptive complexity

0 references

circuit complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Non-commuting graph of a group.

0 references

Computational Complexity

0 references

The isomorphism problem for $k$-trees is complete for logspace

0 references

Reachability is harder for directed than for undirected finite graphs

0 references

On winning strategies in Ehrenfeucht-Fraïssé games

0 references

Graph Isomorphism is in SPP

0 references

Graph isomorphism in quasipolynomial time (extended abstract)

0 references

Q5365126

0 references

Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups

0 references

Construction of finite groups

0 references

Q4234185

0 references

A MILLENNIUM PROJECT: CONSTRUCTING SMALL GROUPS

0 references

Random Graph Isomorphism

0 references

Q4256650

0 references

Subgroups of Abelian Groups

0 references

On the complexity of some problems on groups input as multiplication tables

0 references

Oracle branching programs and Logspace versus $P^*$

0 references

A fast isomorphism test for groups whose Lie algebra has genus 2

0 references

Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps

0 references

Polynomial-time isomorphism test for groups with abelian Sylow towers.

0 references

Combinatorial approaches to the group isomorphism problem

0 references

On the Weisfeiler-Leman dimension of finite groups

0 references

A systematic study of isomorphism invariants of finite groups via the Weisfeiler-Leman dimension

0 references

Quasipolynomial-time canonical form for steiner designs

0 references

An optimal lower bound on the number of variables for graph identification

0 references

Automorphism group computation and isomorphism testing in finite groups

0 references

Count-free Weisfeiler-Leman and group isomorphism

0 references

Problems complete for deterministic logarithmic space

0 references

Multi-stage design for quasipolynomial-time isomorphism testing of Steiner 2-systems

0 references

Graph isomorphism is not $\mathsf{AC}^{0}$-reducible to group isomorphism

0 references

Q5737112

0 references

Graph isomorphism for $K_{3,3}$-free and $K_5$-free graphs is in Log-space

0 references

Nearly linear time isomorphism algorithms for some nonabelian group classes

0 references

Generation of almost simple groups

0 references

Group isomorphism is nearly-linear time for most orders

0 references

Q4298571

0 references

An application of games to the completeness problem for formalized theories

0 references

CONSTRUCTING AUTOMORPHISM GROUPS OF <i>p</i>-GROUPS

0 references

Canonizing Graphs of Bounded Tree Width in Logspace

0 references

Probabilities on finite models

0 references

Q3230355

0 references

Q4535027

0 references

Q5091279

0 references

On the descriptive complexity of groups without abelian normal subgroups (extended abstract)

0 references

On the parallel complexity of Group Isomorphism via Weisfeiler-Leman

0 references

The iteration number of the Weisfeiler-Leman algorithm

0 references

Canonisation and Definability for Graphs of Bounded Rank Width

0 references

Descriptive complexity of finite abelian groups

0 references

Polynomial-time isomorphism test of groups that are tame extensions (extended abstract)

0 references

Algorithms for group isomorphism via group extensions and cohomology

0 references

Descriptive Complexity, Canonisation, and Definable Graph Structure Theory

0 references

Testing Graph Isomorphism in Parallel by Playing a Game

0 references

Definability hierarchies of generalized quantifiers

0 references

Logical hierarchies in PTIME

0 references

Q4650358

0 references

The occurrence of finite groups in the automorphism group of nilpotent groups of class 2

0 references

On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions

0 references

Automorphisms of Finite Abelian Groups

0 references

Upper and lower bounds for first order expressibility

0 references

Relational queries computable in polynomial time

0 references

Q4349673

0 references

Which problems have strongly exponential complexity?

0 references

Finite group theory.

0 references

Completeness results for graph isomorphism.

0 references

Linear time algorithms for Abelian group isomorphism and related problems

0 references

The iteration number of colour refinement

0 references

Factoring Groups Efficiently

0 references

The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3

0 references

Graph isomorphism is low for PP

0 references

From Invariants to Canonization in Parallel

0 references

On the Structure of Polynomial Time Reducibility

0 references

Efficient isomorphism testing for a class of group extensions

0 references

Elements of finite model theory.

0 references

Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model

0 references

Isomorphism in expanding families of indistinguishable groups.

0 references

Stability of nilpotent groups of class 2 and prime exponent

0 references

On the $n\log{n}$ isomorphism technique (preliminary report)

0 references

An exponential lower bound for individualization-refinement algorithms for graph isomorphism

0 references

Describing finite groups by short first-order sentences

0 references

On isomorphism testing of groups with normal Hall subgroups

0 references

Q3941589

0 references

Ehrenfeucht-Fraïssé Games on Random Structures

0 references

Graph isomorphism is in the low hierarchy

0 references

Q5847228

0 references

Representations of finite groups in characteristic $p^r$.

0 references

On the Hardness of Graph Isomorphism

0 references

Characterization of the finite simple groups by spectrum and order.

0 references

An $O(n)$ algorithm for Abelian $p$-group isomorphism and an $O(n \log n)$ algorithm for Abelian group isomorphism

0 references

Graphs of bounded treewidth can be canonized in AC$^1$

0 references

Existence, algorithms, and asymptotics of direct product decompositions. I.

0 references

The threshold for subgroup profiles to agree is $\Omega(\log n)$

0 references

Nondeterministics circuits, space complexity and quasigroups

0 references

Graph isomorphism problem

0 references

Identifiers

DOI

10.1016/J.JCSS.2025.103703

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi On the parallel complexity of group isomorphism via Weisfeiler-Leman