Conferences and lectures

Knots, algorithms and linear programming: the quest to solve unknot recognition in polynomial time

Benjamin Burton (The University of Queensland, Australia)
2013-03-08 10:30-12:00
Room 056, Graduate School of Mathematical Sciences, the University of Tokyo

Abstract: In this talk we explore new approaches to the old and difficult computational problem of unknot recognition.  Although the best known algorithms for this problem run in exponential time, there is increasing evidence that a polynomial time solution might be possible.  We outline several promising approaches, in which computational geometry, linear programming and greedy algorithms all play starring roles.  We finish with a new algorithm that combines techniques from topology and combinatorial optimisation, which is the first to exhibit "real world" polynomial time behaviour: although it is still exponential time in theory, exhaustive experimentation shows that this algorithm can solve unknot recognition for "practical" inputs by running just a linear number of linear programs.

This is joint work with Melih Ozlen.