Count-free Weisfeiler-Leman and group isomorphism

DOI10.1142/S0218196724500103zbMATH Open1544.20002MaRDI QIDQ6545240FDOQ6545240

Authors: Nathaniel A. Collins, Michael Levet

Publication date: 29 May 2024

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Recommendations

On the Weisfeiler-Leman dimension of finite groups
Efficient isomorphism testing for a class of group extensions
Beating the generator-enumeration bound for $p$-group isomorphism

zbMATH Keywords

circuit complexity descriptive complexity group isomorphism Weisfeiler-Leman

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19) Applications of logic to group theory (20A15) Computational methods for problems pertaining to group theory (20-08)

Cites Work

Probabilities on finite models
Computational Complexity
Paths, Trees, and Flowers
Which problems have strongly exponential complexity?
On uniformity within $NC^ 1$
Finite group theory.
Title not available (Why is that?)
On the Structure of Polynomial Time Reducibility
Title not available (Why is that?)
Characterization of the finite simple groups by spectrum and order.
On the Hardness of Graph Isomorphism
Elements of finite model theory.
Title not available (Why is that?)
Title not available (Why is that?)
Automorphism group computation and isomorphism testing in finite groups
CONSTRUCTING AUTOMORPHISM GROUPS OF p-GROUPS
Title not available (Why is that?)
An application of games to the completeness problem for formalized theories
Reachability is harder for directed than for undirected finite graphs
An optimal lower bound on the number of variables for graph identification
Title not available (Why is that?)
Isomorphism of graphs of bounded valence can be tested in polynomial time
Graph Isomorphism is in SPP
Small-diameter Cayley graphs for finite simple groups
Graph isomorphism is in the low hierarchy
Graph isomorphism problem
On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
Completeness results for graph isomorphism.
A MILLENNIUM PROJECT: CONSTRUCTING SMALL GROUPS
Graph isomorphism for $K_{3,3}$-free and $K_5$-free graphs is in Log-space
Isomorphism in expanding families of indistinguishable groups.
Construction of finite groups
Definability hierarchies of generalized quantifiers
On winning strategies in Ehrenfeucht-Fraïssé games
The occurrence of finite groups in the automorphism group of nilpotent groups of class 2
On the $n\log{n}$ isomorphism technique (preliminary report)
Quasipolynomial-time canonical form for steiner designs
Multi-stage design for quasipolynomial-time isomorphism testing of Steiner 2-systems
On the complexity of some problems on groups input as multiplication tables
Title not available (Why is that?)
An $O(n)$ algorithm for Abelian $p$-group isomorphism and an $O(n \log n)$ algorithm for Abelian group isomorphism
Linear time algorithms for Abelian group isomorphism and related problems
Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups
Polynomial-time isomorphism test for groups with abelian Sylow towers.
Existence, algorithms, and asymptotics of direct product decompositions. I.
On isomorphism testing of groups with normal Hall subgroups
A fast isomorphism test for groups whose Lie algebra has genus 2
Title not available (Why is that?)
Efficient isomorphism testing for a class of group extensions
Nearly linear time isomorphism algorithms for some nonabelian group classes
Graph isomorphism in quasipolynomial time (extended abstract)
Upper and lower bounds for first order expressibility
A note on the graph isomorphism counting problem
Logical hierarchies in PTIME
Describing finite groups by short first-order sentences
Stability of nilpotent groups of class 2 and prime exponent
Graphs of bounded treewidth can be canonized in AC$^1$
From Invariants to Canonization in Parallel
Testing Graph Isomorphism in Parallel by Playing a Game
The isomorphism problem for $k$-trees is complete for logspace
Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing
Oracle branching programs and Logspace versus $P^*$
Graph isomorphism is low for PP
Canonizing Graphs of Bounded Tree Width in Logspace
Representations of finite groups in characteristic $p^r$.
Title not available (Why is that?)
Title not available (Why is that?)
Nondeterministics circuits, space complexity and quasigroups
Polynomial-time isomorphism test of groups that are tame extensions (extended abstract)
Descriptive complexity of finite abelian groups
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
Title not available (Why is that?)
The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
Factoring Groups Efficiently
Algorithms for group isomorphism via group extensions and cohomology
On the Weisfeiler-Leman dimension of finite groups
Graph isomorphism is not $\mathsf{AC}^{0}$-reducible to group isomorphism
Ehrenfeucht-Fraïssé Games on Random Structures
An exponential lower bound for individualization-refinement algorithms for graph isomorphism
The threshold for subgroup profiles to agree is $\Omega(\log n)$
On the parallel complexity of Group Isomorphism via Weisfeiler-Leman
Lower bounds for choiceless polynomial time via symmetric XOR-circuits

This page was built for publication: Count-free Weisfeiler-Leman and group isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6545240)