Unknot recognition is quasi-polynomial time

YMSC Topology Seminar

Organizers：

陈伟彦、高鸿灏、黄意、林剑锋、孙巍峰

Speaker：

Marc Lackenby (University of Oxford)

Time：

Thur., 16:00-17:00, Nov. 7, 2024

Online：

Zoom Meeting ID: 405 416 0815

Passcode: 111111

Title：

Unknot recognition is quasi-polynomial time

Abstract:

I will outline a new algorithm for unknot recognition that runs in quasi-polynomial time. The input is a diagram of a knot with n crossings, and the running time is 2^{O((log n)^3)}. The algorithm uses a wide variety of tools from 3-manifold theory, including normal surfaces, hierarchies and Heegaard splittings. In my talk, I will explain this background theory, as well as explain how it fits into the algorithm.