Search and witness problems in group theory

DOI10.1515/GCC.2010.015zbMath1222.20024arXiv1010.0382OpenAlexW2963744260MaRDI QIDQ3085996

Vladimir Shpilrain

Publication date: 1 April 2011

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

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

zbMATH Keywords

stratificationdecision problemssearch problemsconjugacy search problemalgorithmic problemssubgroup membership search problemword search problem

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) Word problems, etc. in computability and recursion theory (03D40) Research exposition (monographs, survey articles) pertaining to group theory (20-02)

Related Items (5)

The status of polycyclic group-based cryptography: a survey and open problems ⋮ Algorithmic problems in Engel groups and cryptographic applications ⋮ Two general schemes of algebraic cryptography ⋮ Search problems in groups and branching processes ⋮ Asymptotic invariants, complexity of groups and related problems

Cites Work

• Average-case complexity and decision problems in group theory.
• A tighter bound for the number of words of minimum length in an automorphic orbit.
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Extended Nielsen transformations and triviality of a group
• Relations among the squares of the generators of the braid group
• Generic-case complexity, decision problems in group theory, and random walks.
• Automorphic orbits in free groups.
• Isoperimetric and isodiametric functions of groups
• Isoperimetric functions of groups and computational complexity of the word problem
• Counting words of minimum length in an automorphic orbit.
• ALGORITHMIC PROBLEMS IN VARIETIES
• Authentication from Matrix Conjugation

This page was built for publication: Search and witness problems in group theory