Conjugacy in Baumslag's group, generic case complexity, and division in power circuits

DOI10.1007/s00453-016-0117-zzbMath1357.68081arXiv1309.5314OpenAlexW1639574001MaRDI QIDQ727969

Armin Weiß, Volker Diekert, Alexei G. Myasnikov

Publication date: 21 December 2016

Published in: Algorithmica, LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

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

zbMATH Keywords

conjugacy problemBaumslag groupdivisibility problemalgorithmic group theorygeneric case complexitypower circuit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (10)

Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem ⋮ The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\) ⋮ Parallel algorithms for power circuits and the word problem of the Baumslag group ⋮ Improved parallel algorithms for generalized Baumslag groups ⋮ Knapsack in graph groups ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ The conjugacy problem for Higman’s group ⋮ The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\) ⋮ Compression techniques in group theory

Uses Software

• CRAG

Cites Work

• Unnamed Item
• Unnamed Item
• 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.
• Group-based cryptography
• Generic-case complexity, decision problems in group theory, and random walks.
• Combinatorial group theory.
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Combinatorial group theory and public key cryptography
• Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem
• Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P
• Evolutionary algorithm solution of the multiple conjugacy search problem in groups, and its applications to cryptography
• Cogrowth of Regular Graphs
• Random Walks on Infinite Graphs and Groups - a Survey on Selected topics
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces
• POWER CIRCUITS, EXPONENTIAL ALGEBRA, AND TIME COMPLEXITY
• Random Walks on Infinite Graphs and Groups
• Authentication from Matrix Conjugation
• GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS
• A non-cyclic one-relator group all of whose finite quotients are cyclic

This page was built for publication: Conjugacy in Baumslag's group, generic case complexity, and division in power circuits