Compressed decision problems in hyperbolic groups

DOI10.4230/LIPICS.STACS.2019.37MaRDI QIDQ5090487FDOQ5090487

Authors: Derek F. Holt, Markus Lohrey, Saul Schleimer 

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1808.06886

Recommendations

• Compressed decision problems in hyperbolic groups
• Knapsack in hyperbolic groups
• The compressed conjugacy problem in relatively hyperbolic groups
• Knapsack in hyperbolic groups
• Efficient Computation in Groups Via Compression

zbMATH Keywords

hyperbolic groupsalgorithms for compressed wordscircuit evaluation problems

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithmics on SLP-compressed strings: a survey
• Research announcement: The structure of groups with a quasiconvex hierarchy.
• A FAST ALGORITHM FOR STALLINGS' FOLDING PROCESS
• The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
• ALMOST EVERY GROUP IS HYPERBOLIC
• Knapsack problems in groups
• Knapsack problems in products of groups
• Polynomial-time word problems.
• Coxeter groups are virtually special
• Title not available (Why is that?)
• The isomorphism problem for all hyperbolic groups.
• The Smallest Grammar Problem
• Finite Monoids: From Word to Circuit Evaluation
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• Title not available (Why is that?)
• Power circuits, exponential algebra, and time complexity
• The simultaneous conjugacy problem in groups of piecewise linear functions.
• The complexity of Grigorchuk groups with application to cryptography
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Title not available (Why is that?)
• Word Problems and Membership Problems on Compressed Words
• Compressed words and automorphisms in fully residually free groups.
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• Knapsack in graph groups
• Groups, languages and automata
• The Compressed Word Problem for Groups
• Evaluation of circuits over nilpotent and polycyclic groups
• Title not available (Why is that?)
• Compressed decision problems for graph products and applications to (outer) automorphism groups.
• Knapsack problems for wreath products
• Knapsack in hyperbolic groups
• Low-complexity computations for nilpotent subgroup problems
• The conjugacy problem in hyperbolic groups for finite lists of group elements.
• Ackermannian integer compression and the word problem for hydra groups
• Efficient algorithms for highly compressed data: the word problem in Higman's group is in P.

Cited In (11)

• Logspace and compressed-word computations in nilpotent groups
• Algorithms for contractibility of compressed curves on 3-manifold boundaries
• The power word problem in graph products
• Knapsack in hyperbolic groups
• Compressed decision problems in hyperbolic groups
• Complexity of word problems for HNN-extensions
• Post's Correspondence Problem for hyperbolic and virtually nilpotent groups
• Compression techniques in group theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• The compressed conjugacy problem in relatively hyperbolic groups

This page was built for publication: Compressed decision problems in hyperbolic groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090487)