Séance Séminaire

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

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.