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

CREATORMark C. Bell, Saul Schleimer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-02459

Browse the full library · About the Tower of Babel