清华主页 EN
导航菜单

Unknot recognition is quasi-polynomial time

来源: 11-06

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

地点:Zoom Meeting ID: 405 416 0815 Passcode: 111111

主讲人:Marc Lackenby (University of Oxford)

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.

返回顶部
相关文章
  • Parametric polynomial preserving recovery on manifolds

    AbstractIn this talk, we will introduce gradient recovery schemes for data defined on discretized manifolds. The proposed method, parametric polynomial preserving recovery (PPPR), does not require the tangent spaces of the exact manifolds which have been assumed for some significant gradient recovery methods in the literature. Another advantage of PPPR is that superconvergence is guaranteed wit...

  • YMSC Topology Seminar | An L^2-version of Alexander polynomial and 3-dimensional topology

    Abstract:The L^2-Alexander torsion is an invariant associated to a 3-manifold and an 1-cohomology class. This invariant is a real function with many properties similar to / generalizing the tranditional Alexander polynomial. In this talk, I will discuss the "leading coefficient" of this function and show its connection with sutured manifold theory