Compressed decision problems in hyperbolic groups

DOI10.4230/LIPICS.STACS.2019.37MaRDI QIDQ5090487zbMATH OpenFDO

Authors Derek F. Holt, Markus Lohrey, Saul Schleimer

Publication date 18 July 2022

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

zbMATH Keywords

algorithms for compressed wordscircuit evaluation problemshyperbolic groups

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

Cites work

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

Cited in

(13)

• Compression techniques in group theory
• The power word problem
• Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
• Logspace and compressed-word computations in nilpotent groups
• Complexity of word problems for HNN-extensions
• Knapsack in hyperbolic groups
• Algorithms for contractibility of compressed curves on 3-manifold boundaries
• Post's Correspondence Problem for hyperbolic and virtually nilpotent groups
• The compressed conjugacy problem in relatively hyperbolic groups
• The power word problem in graph products
• Compressed decision problems in hyperbolic groups
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• Algorithms for contractibility of compressed curves on 3-manifold boundaries

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)