On the descriptive complexity of groups without abelian normal subgroups (extended abstract)
From MaRDI portal
Cites work
- A fast isomorphism test for groups whose Lie algebra has genus 2
- A MILLENNIUM PROJECT: CONSTRUCTING SMALL GROUPS
- Algorithms based on \(*\)-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing
- 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 optimal lower bound on the number of variables for graph identification
- Automorphism group computation and isomorphism testing in finite groups
- Canonisation and definability for graphs of bounded rank width
- 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
- Existence, algorithms, and asymptotics of direct product decompositions. I.
- Factoring Groups Efficiently
- Generalizations of k-dimensional Weisfeiler-Leman stabilization
- 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 Identified by Logics with Counting
- Group isomorphism is nearly-linear time for most orders
- scientific article; zbMATH DE number 6003856 (Why is no real title available?)
- scientific article; zbMATH DE number 3115890 (Why is no real title available?)
- scientific article; zbMATH DE number 1284153 (Why is no real title available?)
- scientific article; zbMATH DE number 1318518 (Why is no real title available?)
- scientific article; zbMATH DE number 6783478 (Why is no real title available?)
- Isomorphism in expanding families of indistinguishable groups.
- Linear time algorithms for Abelian group isomorphism and related problems
- Logical hierarchies in PTIME
- Nearly linear time isomorphism algorithms for some nonabelian group classes
- On a generalization of quantifiers
- On fixed-point logic with counting
- 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 Structure of Polynomial Time Reducibility
- On the Weisfeiler-Leman dimension of finite groups
- On winning strategies in Ehrenfeucht-Fraïssé games
- PEBBLE GAMES AND LINEAR EQUATIONS
- Pebble games with algebraic rules
- 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)
- Polynomial-time theory of matrix groups
- Reachability is harder for directed than for undirected finite graphs
- Relational queries computable in polynomial time
- Stability of nilpotent groups of class 2 and prime exponent
- Testing Graph Isomorphism in Parallel by Playing a Game
- The iteration number of colour refinement
- The logic of graph neural networks
- 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
- Which problems have strongly exponential complexity?
Cited in
(5)- The minimal faithful permutation degree of groups without abelian normal subgroups
- Complexity of minimal faithful permutation degree for fitting-free groups
- 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
This page was built for publication: On the descriptive complexity of groups without abelian normal subgroups (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6940529)
