Nearly-Linear Solution to the Word Problem for 3-Manifold Groups
Abstract
Abstract We show that the word problem for any 3-manifold group is solvable in time $O(n\log ^{3} n)$. Our main contribution is the proof that the word problem for admissible graphs of groups, in the sense of Croke and Kleiner, is solvable in $O(n\log n)$; this covers fundamental groups of non-geometric graph manifolds. Similar methods also give that the word problem for free products can be solved “almost as quickly” as the word problem in the factors.
Fields of Study & Subjects
Geometric and Algebraic Topology
semigroups and automata theory
Finite Group Theory Research
Publication details
- Journal / source
- International Mathematics Research Notices
- Volume
- 2026
- Issue
- 4
- Publication date
- 19 January 2026
- Language
- EN