The word problem for the mapping class group in quasi-linear time
Mark C. Bell, Saul Schleimer · 2025
Read The word problem for the mapping class group in quasi-linear time by Mark C. Bell, Saul Schleimer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-02459.txt.
Description
Mark Bell and Saul Schleimer, mathematicians in geometric topology, settle the running time of a basic decision problem about surfaces. The mapping class group of a compact surface collects all the ways the surface can be deformed and twisted onto itself, up to continuous deformation. Its word problem asks: given a word written in the group's generators, does it represent the identity, the deformation that does nothing overall?
The authors give an algorithm that answers the question in quasi-linear time, on the order of n times the cube of the logarithm of n for an input of length n. That is essentially as fast as reading the input a few times over. Word problems are the most basic algorithmic question one can ask about a group. For mapping class groups, which encode the symmetries of surfaces, an efficient solution anchors a wider theory of computation with curves and surfaces.
Catalog record
| CREATOR | Mark C. Bell, Saul Schleimer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-02459