Return to Colloquia & Seminar listing
Fast normal surface theoryGeometry/Topology
|Speaker:||Alex Coward, University of Sydney, Australia|
|Start time:||Tue, Feb 5 2013, 3:10PM|
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.