Improved parallel algorithms for generalized Baumslag groups

DOI10.1007/978-3-031-20624-5_40arXiv2206.06181OpenAlexW4312951391MaRDI QIDQ6164005

Caroline Mattes, Armin Weiß

Publication date: 26 July 2023

Published in: LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

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

zbMATH Keywords

word problemparallel complexityconjugacy problemBaumslag groupalgorithmic group theorypower circuit\( \mathsf{TC}^1 \)

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (2)

Parallel algorithms for power circuits and the word problem of the Baumslag group ⋮ Improved parallel algorithms for generalized Baumslag groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• Average-case complexity and decision problems in group theory.
• Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
• Group-based cryptography
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• Generic-case complexity, decision problems in group theory, and random walks.
• Combinatorial group theory.
• Evaluation of circuits over nilpotent and polycyclic groups
• Isoperimetric and isodiametric functions of groups
• Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Word Problems Solvable in Logspace
• POWER CIRCUITS, EXPONENTIAL ALGEBRA, AND TIME COMPLEXITY
• EFFICIENT ALGORITHMS FOR HIGHLY COMPRESSED DATA: THE WORD PROBLEM IN HIGMAN'S GROUP IS IN P
• The conjugacy problem for Higman’s group
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• A non-cyclic one-relator group all of whose finite quotients are cyclic
• A Finitely Generated Infinite Simple Group
• The word problem
• The word problem
• Improved parallel algorithms for generalized Baumslag groups
• Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group.

This page was built for publication: Improved parallel algorithms for generalized Baumslag groups