Sublinear time algorithms in the theory of groups and semigroups.

zbMath1234.20044arXiv1105.3252MaRDI QIDQ716397

Vladimir Shpilrain

Publication date: 28 April 2011

Published in: Illinois Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

complexityprimitive elementsword problemalgorithmic problemssublinear time algorithms

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Free semigroups, generators and relations, word problems (20M05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Word problems, etc. in computability and recursion theory (03D40)

Related Items (3)

Average-case complexity of the Whitehead problem for free groups ⋮ Randomness and complexity in matrix groups ⋮ On two-generator subgroups in \(\mathrm{SL}_2(\mathbb{Z})\), \(\mathrm{SL}_2(\mathbb{Q})\), and \(\mathrm{SL}_2(\mathbb{R})\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
• On the distance between the expressions of a permutation
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Introductory notes on Richard Thompson's groups
• Generic-case complexity, decision problems in group theory, and random walks.
• Combinatorial group theory.
• Beziehungen zwischen Gruppen und Idealen in einem speziellen Ring
• Property testing and its connection to learning and approximation
• Expected Computation Time for Hamiltonian Path problem
• Braids, Links, and Mapping Class Groups. (AM-82)
• ALGORITHMIC PROBLEMS IN VARIETIES
• MAGNUS EMBEDDINGS FOR SEMIGROUPS
• Subsemigroups of nilpotent groups
• Free differential calculus. IV: The quotient groups of the lower central series
• Relatively free semigroups of intermediate growth
• Efficient testing of large graphs

This page was built for publication: Sublinear time algorithms in the theory of groups and semigroups.