Type: Seminar

Distribution: World

Expiry: 6 May 2013

Auth: zhangou@como.maths.usyd.edu.au

Speaker: Benjamin Burton (Queensland) http://www.maths.uq.edu.au/~bab/ Time: Thursday, April 18, 12NOON--1PM Room: Carslaw 829, AGR Lunch: after the talk. The reservation at Law Annex Cafe is at 1:10PM. ---------------------------------------------- Title: Untangling Knots Using Combinatorial Optimisation Abstract: unknot recognition is the algorithmic problem of determining whether a knot (i.e., a closed loop) in 3-dimensional space can be untangled. It is a major unsolved problem as to whether this problem has a fast polynomial time solution. Here we present the first conclusive algorithm for unknot recognition which, although exponential time in theory, exhibits a clear polynomial time behaviour in exhaustive practical experiments. The algorithm makes significant use of techniques from combinatorial optimisation, and uses a branch-and-bound framework with linear programming steps. We also introduce the topological software package Regina (in which the algorithm was implemented), and discuss the relevance of our results to other difficult problems in computational topology. This is joint work with Melih Ozlen. ---------------------------------------------- Seminar website: http://www.maths.usyd.edu.au/u/SemConf/Geometry/