Title: Exploring parameterised complexity in computational topology
Speaker: Benjamin A. Burton, The University of Queensland, Australia
Date: 12 November 2015
Time: 4:00 pm
Venue: LH 1
Exact computation with knots and 3-manifolds is challenging - many fundamental problems are decidable but enormously complex, and many major algorithms have never been implemented. Even simple problems, such as unknot recognition (testing whether a loop of string is knotted), or 3-sphere recognition (testing whether a triangulated 3-manifold is topologically trivial), have best-known algorithms that are worst-case exponential time.