Random van Kampen diagrams and algorithmic problems in groups

DOI10.1515/gcc.2011.006zbMath1284.20032OpenAlexW2000976823MaRDI 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 algorithmsword problemfinitely presented groupssearch algorithmsfilling functionsTodd-Coxeter algorithmhyperbolic diagramsrandom van Kampen diagrams

Mathematics Subject Classification ID

Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Hyperbolic groups and nonpositively curved groups (20F67) Cancellation theory of groups; application of van Kampen diagrams (20F06) Probabilistic methods in group theory (20P05)

Related Items (5)

Random equations in free groups ⋮ Random equations in nilpotent groups. ⋮ An improved version of the AAG cryptographic protocol ⋮ Conjugacy search problem and the Andrews-Curtis conjecture ⋮ Knapsack problems in 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

This page was built for publication: Random van Kampen diagrams and algorithmic problems in groups