Solving the word problem in the mapping class group in quasi-linear time

Abstract: 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öller's version of the half-GCD algorithm, and a delicate error analysis in interval arithmetic.

This is joint work with Mark Bell.

algebraic topologydifferential geometrydynamical systemsgroup theorygeometric topologysymplectic geometry

Audience: researchers in the topic

Geometry and topology online

Series comments: You can also find up-to-date information on the seminar homepage - warwick.ac.uk/fac/sci/maths/research/events/seminars/areas/geomtop/

The talks start at 13:30. Talks are typically fifty minutes long, with ten minutes for questions.