Random van Kampen diagrams and algorithmic problems in groups.

DOI10.1515/GCC.2011.006MaRDI QIDQ2882828zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)