Count-free Weisfeiler-Leman and group isomorphism
From MaRDI portal
Publication:6545240
Computational methods for problems pertaining to group theory (20-08) 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) Analysis of algorithms and problem complexity (68Q25)
The authors investigate the significance of counting in group isomorphism. They begin by utilizing the count-free variant of the Weisfeiler-Leman version I algorithm for groups [\textit{J. Brachter} and \textit{P. Schweitzer}, in: Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8--11, 2020. New York, NY: Association for Computing Machinery (ACM). 287--300 (2020; Zbl 1498.20002)], combined with bounded non-determinism and limited counting, to enhance the parallel complexity of isomorphism testing for several families of groups. They demonstrate that the \(q\)-ary count-free pebble game fails to distinguish even abelian groups.
Recommendations
Cites work
- A fast isomorphism test for groups whose Lie algebra has genus 2
- A MILLENNIUM PROJECT: CONSTRUCTING SMALL GROUPS
- 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 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
- 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
- CONSTRUCTING AUTOMORPHISM GROUPS OF p-GROUPS
- Construction of finite groups
- Definability hierarchies of generalized quantifiers
- Describing finite groups by short first-order sentences
- Descriptive complexity of finite abelian groups
- Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
- 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 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 SPP
- 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
- 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?)
- 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 \(n\log{n}\) isomorphism technique (preliminary report)
- On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
- On the complexity of some problems on groups input as multiplication tables
- On the Hardness of Graph Isomorphism
- On the parallel complexity of Group Isomorphism via Weisfeiler-Leman
- On the Structure of Polynomial Time Reducibility
- On the Weisfeiler-Leman dimension of finite groups
- 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 abelian Sylow towers.
- Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups
- 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 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)
- The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
- Upper and lower bounds for first order expressibility
- Which problems have strongly exponential complexity?
Cited in
(5)- The minimal faithful permutation degree of groups without abelian normal subgroups
- Complexity of identifying fitting-free groups
- On the descriptive complexity of groups without abelian normal subgroups
- On the parallel complexity of group isomorphism via Weisfeiler-Leman
- Parallel complexity of identifying groups and quasigroups via decompositions
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)
