Count-free Weisfeiler-Leman and group isomorphism

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)

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

Cites work

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

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)