Random van Kampen diagrams and algorithmic problems in groups

DOI10.1515/gcc.2011.006zbMath1284.20032MaRDI QIDQ2882828

Alexander Ushakov, Alexei G. Myasnikov

Publication date: 7 May 2012

Published in: Groups – Complexity – Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/gcc.2011.006

zbMATH Keywords

fast algorithms; word problem; finitely presented groups; search algorithms; filling functions; Todd-Coxeter algorithm; hyperbolic diagrams; random van Kampen diagrams

Mathematics Subject Classification ID

20F65: Geometric group theory

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

20F67: Hyperbolic groups and nonpositively curved groups

20F06: Cancellation theory of groups; application of van Kampen diagrams

20P05: Probabilistic methods in group theory

Related Items

Knapsack problems in groups, Random equations in nilpotent groups., An improved version of the AAG cryptographic protocol, Conjugacy search problem and the Andrews-Curtis conjecture, Random equations in free groups

Cites Work

• Average-case complexity and decision problems in group theory.
• Topology of finite graphs
• Generic-case complexity, decision problems in group theory, and random walks.
• Stallings foldings and subgroups of free groups
• A FAST ALGORITHM FOR STALLINGS' FOLDING PROCESS
• MULTIPLICATIVE MEASURES ON FREE GROUPS