Presented by: 
Clément Maria, UQ
Date: 
Tue 6 Sep, 3:00 pm - 4:00 pm
Venue: 
67-442

Easy instances in computational topology.

Given a computational problem, the very first question in complexity theory is: "Is this problem hard to solve in general?". When the answer is affirmative, the second question is always: "But, which instances of the problem are 'easy'?".

In low-dimensional topology, most interesting properties one would like to extract from a triangulated 3-manifold are extremely hard --- in a complexity theoretical sense --- to compute in the general case. Additionally, the concept of 'easy instance' is not well defined. This talk focuses on the computation of quantum invariants of 3-manifolds, from the perspective of parameterised complexity. We discuss the notion of 'easy instances' for triangulated manifolds, and present two parameters --- one combinatorial, one topological --- for fixed parameter tractable algorithms to compute quantum invariants.

Specifically, we introduce a fixed parameter tractable algorithm in the treewidth of the dual of the triangulation, and a fixed parameter tractable algorithm in the dimension of the first homology group of the underlying manifold. Both algorithms solve #P-hard problems. This is joint work with Ben Burton and Jonathan Spreer.