| School of Mathematical Sciences Colloquium Series | |
Unknot recognition and the elusive
polynomial time algorithm
by
Dr Ben Burton
Date: Friday, 18 May, 2012
Time:
15:10 Location: B.21 Ingkarni
Wardli
Abstract: What do
practical topics such as linear programming
and greedy heuristics have to do with theoretical problems such as
unknot recognition and the Poincare conjecture? In this talk we explore
new approaches to old and difficult computational problems from
geometry and topology: how to tell whether a loop of string is knotted,
or whether a 3-dimensional space has no interesting topological
features. Although the best known algorithms for these problems 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.
The Colloquium will be followed by a reception for our speaker in
the Staff Tea Room with wine and nibbles to which all are invited.