Mapping class groups of surfaces are of fundamental importance in dynamics, geometric group theory, and
low-dimensional topology.  The word problem for groups in general, the definition of the mapping class group, its finite generation by twists, and the solution to its word problem were all set out by Dehn [1911, 1922, 1938].  Some of this material was rediscovered by Lickorish [1960’s] and then by Thurston [1970-80’s] – they gave
important applications of the mapping class group to the topology and geometry of three-manifolds.  In the past fifty years, various mathematicians (including Penner, Mosher, Hamidi-Tehrani, Dylan Thurston, Dynnikov) have given solutions to the word problem in the mapping class group, using a variety of techniques.  All of these algorithms are quadratic-time.

We give an algorithm requiring only $O(n \log^3(n))$ time.  We do this by combining Dynnikov’s approach to curves on surfaces, M"oller’s version of the half-GCD algorithm, and a delicate error analysis in interval arithmetic.

This is joint work with Mark Bell.