Séminaire Algèbre Géométrie Algébrique Topologie Algébrique :

Le 10 octobre 2024 à 10:00 - salle 430

Présentée par Maria Clément - Centre Inria d'Université Côte d'Azur

Some aspects of computational complexity and applications to low dimensional topology

In the first part of this talk, I will introduce general concepts of computational complexity, in particular the complexity classes P, NP and #P, as well as the principle of reduction in complexity. I will also introduce some algorithm paradigm (dynamic programming) for hard problems, exploiting measures of sparsity of a graph (treewidth) in the context of parameterized complexity. In the second part of the talk, I will illustrate how these techniques can be applied to compute quantum invariants of 3-manifolds with provably and practically fast algorithms.