Random van Kampen diagrams and algorithmic problems in groups.

DOI10.1515/GCC.2011.006zbMATH Open1284.20032OpenAlexW2000976823MaRDI QIDQ2882828FDOQ2882828

Authors: Alexander Ushakov, Alexei 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

Recommendations

• SOME SMALL CANCELLATION PROPERTIES OF RANDOM GROUPS
• The geometry of the word problem for finitely generated groups.
• Generic-case complexity, decision problems in group theory, and random walks.
• scientific article; zbMATH DE number 998573
• COMPUTATION IN WORD-HYPERBOLIC GROUPS

zbMATH Keywords

fast algorithmsword problemsearch algorithmsfinitely presented groupsfilling functionsTodd-Coxeter algorithmhyperbolic diagramsrandom van Kampen diagrams

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2882828)