Return to Colloquia & Seminar listing
Fast normal surface theory
Geometry/Topology| Speaker: | Alex Coward, University of Sydney, Australia |
| Location: | 2112 MSB |
| Start time: | Tue, Feb 5 2013, 3:10PM |
Description
Normal surface theory was developed in the 1960's to
algorithmically solve decision problems about triangulated
3-manifolds, such as the unknot recognition problem and the
homeomorphism problem for 3-manifolds.
Traditionally normal surface theory has been regarded as very slow,
both in theory and in practice. Algorithmic complexity and other
bounds were expected to be exponential at best, even for comparatively
simple problems like unknot recognition, and with solutions to
problems like the 3-manifold homeomorphism problem expected to run
with time complexity an iterated exponential in terms of the number of
tetrahedra in the input 3-manifolds.
In this talk we will look at how this perception is turning out to be
unfounded in many cases. In particular I will discuss recent practical
work with Ben Burton and Stephan Tillmann that practically tests
whether a knot complement contains a closed essential surface,
something that would until recently have been regarded as completely
infeasible. We will also talk about how normal surface theory can be
used to prove theoretical upper bounds on complexity.