Linear average-case complexity of algorithmic problems in groups

DOI10.1016/J.JALGEBRA.2025.01.013MaRDI QIDQ7008558zbMATH OpenFDO

Authors Alexander Y. Olshanskii, Vladimir Shpilrain

Publication date 21 March 2025

Published in Journal of Algebra (Search for Journal in Brave)

zbMATH Keywords

nilpotent groupword problemmatrix groupaverage-case complexity

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) Nilpotent groups (20F18) Other matrix groups over fields (20H20) Computational methods for problems pertaining to group theory (20-08)

Cites work

• scientific article; zbMATH DE number 3746135 (Why is no real title available?)
• scientific article; zbMATH DE number 3762288 (Why is no real title available?)
• scientific article; zbMATH DE number 3779604 (Why is no real title available?)
• scientific article; zbMATH DE number 51735 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3440002 (Why is no real title available?)
• scientific article; zbMATH DE number 1836314 (Why is no real title available?)
• Algorithmic problems for metabelian groups
• Algorithmic theory of free solvable groups: randomized computations.
• Algorithmically complex residually finite groups
• Average Case Complete Problems
• Average-case complexity and decision problems in group theory.
• Braid groups are linear
• Braid groups are linear
• Cogrowth and amenability of discrete groups
• FOLDINGS, GRAPHS OF GROUPS AND THE MEMBERSHIP PROBLEM
• Fast multiplication of large numbers
• Generic-case complexity, decision problems in group theory, and random walks.
• Geometry of the conjugacy problem in lamplighter groups
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• Integer multiplication in time \(O(n\log n)\)
• Introductory notes on Richard Thompson's groups
• Isoperimetric functions of groups and computational complexity of the word problem
• Logspace and compressed-word computations in nilpotent groups
• On Infinite Soluble Groups (II)
• On finitely generated soluble linear groups
• On one method for fast approximation of zeta constants by rational fractions
• Ramanujan's master theorem
• Random Walks on Infinite Graphs and Groups
• Random van Kampen diagrams and algorithmic problems in groups.
• Shorter Notes: Representations of Polycyclic Groups
• Sublinear time algorithms in the theory of groups and semigroups.
• The Degree of Polynomial Growth of Finitely Generated Nilpotent Groups
• Thompson’s Group and Public Key Cryptography
• Varieties of groups
• Varieties of soluble groups and a dichotomy of P. Hall

Cited in

(1)

• Nearly-linear solution to the word problem for 3-manifold groups

This page was built for publication: Linear average-case complexity of algorithmic problems in groups

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