Breaking complexity barriers in low-dimensional topology

Orateur: Clément MARIA
Localisation: INRIA, France
Type: Groupe de travail théorie du min-max
Site: UGE
Salle: 4B05R
Date de début: 14/03/2017 - 15:45
Date de fin: 14/03/2017 - 15:45

In this talk, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariants $TV_{4,q}$, using the dimension of the first homology group of the $3$-manifold as parameter. The computation of $TV_{4,q}$ is known to be #P-hard in general; using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the large family of $3$-manifolds with first homology group of bounded rank. After giving an overview of complexity theory in low-dimensional topology, we will give details on the construction of the algorithm, relying on a new topological interpretation of the invariant $TV_{4,q}$.