Compression techniques in group theory

DOI10.1007/978-3-030-80049-9_30OpenAlexW3184112958MaRDI QIDQ2117795

Markus Lohrey

Publication date: 22 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-80049-9_30

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

The fully compressed subgroup membership problem

Uses Software

• CRAG

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hydra groups.
• 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.
• Compressed word problems in HNN-extensions and amalgamated products
• Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
• The Nielsen reduction and P-complete problems in free groups
• Polynomial-time word problems.
• Coxeter groups are virtually special
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• On finitely generated soluble linear groups
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• Generic-case complexity, decision problems in group theory, and random walks.
• Evaluation of circuits over nilpotent and polycyclic groups
• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
• Progress on Polynomial Identity Testing-II
• Algorithmics on SLP-compressed strings: A survey
• Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• On the algorithmic insolvability of the word problem in group theory
• Primality and identity testing via Chinese remaindering
• Efficient Computation in Groups Via Compression
• The Smallest Grammar Problem
• COMPRESSED WORDS AND AUTOMORPHISMS IN FULLY RESIDUALLY FREE GROUPS
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Word Problems Solvable in Logspace
• Finite Monoids: From Word to Circuit Evaluation
• Taming the hydra: The word problem and extreme integer compression
• POWER CIRCUITS, EXPONENTIAL ALGEBRA, AND TIME COMPLEXITY
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• Parallel identity testing for skew circuits with big powers and applications
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
• COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS
• The Structure of Groups with a Quasiconvex Hierarchy
• Membership Problem for the Modular Group
• The Compressed Word Problem for Groups
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Word Problems and Membership Problems on Compressed Words
• Computable Algebra, General Theory and Theory of Computable Fields
• Hierarchies of Computable groups and the word problem
• The word problem
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Compression techniques in group theory