Algorithmic problems in right-angled Artin groups: complexity and applications
From MaRDI portal
Abstract: In this paper we consider several classical and novel algorithmic problems for right-angled Artin groups, some of which are closely related to graph theoretic problems, and study their computational complexity. We study these problems with a view towards applications to cryptography.
Recommendations
- An introduction to right-angled Artin groups.
- The conjugacy problem in subgroups of right-angled Artin groups
- Algorithmic problems in Engel groups and cryptographic applications
- Compressed decision problems for graph products and applications to (outer) automorphism groups.
- The complexity of Grigorchuk groups with application to cryptography
Cites work
- scientific article; zbMATH DE number 5982274 (Why is no real title available?)
- scientific article; zbMATH DE number 3910294 (Why is no real title available?)
- scientific article; zbMATH DE number 3938048 (Why is no real title available?)
- scientific article; zbMATH DE number 3563392 (Why is no real title available?)
- scientific article; zbMATH DE number 3630641 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1424314 (Why is no real title available?)
- A Generating Set for the Automorphism Group of a Graph Group
- A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry
- A practical cryptanalysis of \({\mathrm {walnutdsa}^{\mathrm {TM}}}\)
- A secret sharing scheme based on group presentations and the word problem
- Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
- Algorithms for maximum independent sets
- An introduction to right-angled Artin groups.
- An obstruction to embedding right-angled Artin groups in mapping class groups
- Anti-trees and right-angled Artin subgroups of braid groups
- Authentication schemes from actions on graphs, groups, or rings
- Automorphisms of graph groups.
- Coding and Cryptography
- Combinatorial problems of commutation and rearrangements
- Complexity of graph embeddability problems
- Conjugacy \(p\)-separability of right-angled Artin groups and applications.
- Divergence and quasimorphisms of right-angled Artin groups.
- Edge decompositions into two kinds of graphs
- Efficient solution of some problems in free partially commutative monoids
- Embeddability and Universal Theory of Partially Commutative Groups
- Embeddability between right-angled Artin groups..
- Finiteness properties of automorphism groups of right-angled Artin groups
- Forests, frames, and games: Algorithms for matroid sums and applications
- Free Lie algebras and free monoids. Bases of free Lie algebras and factorizations of free monoids
- Graph algebras
- Homology of certain algebras defined by graphs
- How to share a secret
- Interpretierbarkeit in der Gruppentheorie
- Isomorphisms of Graph Groups
- Logspace computations in graph groups and Coxeter groups.
- NP-completeness of graph decomposition problems
- On public-key cryptosystems based on combinatorial group theory
- On the subgroups of right-angled Artin groups and mapping class groups
- Recognition of subgroups of direct products of hyperbolic groups
- Shortlex automaticity and geodesic regularity in Artin groups.
- Special cube complexes
- Subgraph isomorphism in graph classes
- The NP-Completeness of Edge-Coloring
- The NP-Completeness of Some Edge-Partition Problems
- The conjugacy problem in subgroups of right-angled Artin groups
- The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
Cited in
(6)- An algebraic characterization of 𝑘–colorability
- Expanders and right-angled Artin groups
- Geometry and Combinatorics via Right-Angled Artin Groups
- Algorithmic problems in Engel groups and cryptographic applications
- Hamiltonicity via cohomology of right-angled Artin groups
- The relative exponential growth rate of subgroups of acylindrically hyperbolic groups
This page was built for publication: Algorithmic problems in right-angled Artin groups: complexity and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1628497)
