Count-free Weisfeiler-Leman and group isomorphism

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

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Characterization of the finite simple groups by spectrum and order.
A fast isomorphism test for groups whose Lie algebra has genus 2
Elements of finite model theory.
The isomorphism problem for $k$-trees is complete for logspace
Small-diameter Cayley graphs for finite simple groups
Graph isomorphism problem
Graph isomorphism is in the low hierarchy
Representations of finite groups in characteristic $p^r$.
Isomorphism of graphs of bounded valence can be tested in polynomial time
Upper and lower bounds for first order expressibility
Oracle branching programs and Logspace versus $P^*$
An optimal lower bound on the number of variables for graph identification
Graph isomorphism is low for PP
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
A note on the graph isomorphism counting problem
On winning strategies in Ehrenfeucht-Fraïssé games
Construction of finite groups
Nondeterministics circuits, space complexity and quasigroups
Automorphism group computation and isomorphism testing in finite groups
Completeness results for graph isomorphism.
Which problems have strongly exponential complexity?
Describing finite groups by short first-order sentences
An $O(n)$ algorithm for Abelian $p$-group isomorphism and an $O(n \log n)$ algorithm for Abelian group isomorphism
Logical hierarchies in PTIME
Definability hierarchies of generalized quantifiers
The occurrence of finite groups in the automorphism group of nilpotent groups of class 2
On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
Graph Isomorphism is in SPP
On uniformity within $NC^ 1$
Linear time algorithms for Abelian group isomorphism and related problems
Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups
Existence, algorithms, and asymptotics of direct product decompositions, I
Isomorphism in expanding families of indistinguishable groups
Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
Graph Isomorphism is Not AC0-Reducible to Group Isomorphism
Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$
DESCRIPTIVE COMPLEXITY OF FINITE ABELIAN GROUPS
An application of games to the completeness problem for formalized theories
Polynomial-Time Isomorphism Test of Groups that are Tame Extensions
Reachability is harder for directed than for undirected finite graphs
From Invariants to Canonization in Parallel
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
Testing Graph Isomorphism in Parallel by Playing a Game
Factoring Groups Efficiently
Ehrenfeucht-Fraïssé Games on Random Structures
Stability of nilpotent groups of class 2 and prime exponent
On the Structure of Polynomial Time Reducibility
Probabilities on finite models
CONSTRUCTING AUTOMORPHISM GROUPS OF p-GROUPS
Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing
On the Hardness of Graph Isomorphism
A MILLENNIUM PROJECT: CONSTRUCTING SMALL GROUPS
Canonizing Graphs of Bounded Tree Width in Logspace
On the Weisfeiler-Leman Dimension of Finite Groups
The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
The threshold for subgroup profiles to agree is $\Omega(\log n)$
An exponential lower bound for individualization-refinement algorithms for graph isomorphism
Algorithms for Group Isomorphism via Group Extensions and Cohomology
Computational Complexity
Paths, Trees, and Flowers
Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
Graph isomorphism in quasipolynomial time [extended abstract]
On the n^{log n} isomorphism technique (A Preliminary Report)
Quasipolynomial-time canonical form for steiner designs
Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems
Nearly linear time isomorphism algorithms for some nonabelian group classes
On the complexity of some problems on groups input as multiplication tables
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