Séminaire Francilien de Géométrie Algorithmique et Combinatoire

Le Séminaire de Géométrie Algorithmique et Combinatoire vise à regrouper des exposés dans ce domaine au sens le plus large, et dans les disciplines connexes en mathématiques et informatique. Il est ouvert à tous les chercheurs et étudiants intéressés. Les exposés sont destinés à un public large.

Il se tient un jeudi par mois, de 14h à 17h, à l'Institut Henri Poincaré à Paris (plan d'accès), en salle 201.

Pour recevoir les annonces de ce séminaire, envoyer un message à vincent [dot-sign] pilaud [the-funny-at-sign] lix [dot-sign] polytechnique [dot-sign] fr.

La liste des exposés passés est disponible ici.


15 mars 2018
14h Xavier Allamigeon CMAP, École Polytechnique
TBA
15h30 Éric Colin de Verdière LIGM, CNRS & Univ. Marne-la-Vallée
Deciding contractibility of curves on the boundary of a $3$-manifold
In $3$-dimensional computational topology, one of the most important problems is the unknot problem: Is an input simple closed curve in $R^3$ unknotted? The seminal result by Hass, Lagarias, and Pippenger [JACM 1999] shows that the problem is in NP. Very recently, Lackenby proved that the problem is also in coNP. However, no subexponential-time algorithm is known.
I will briefly describe Hass et al.'s method, based on normal surface theory, and will explain why it provides an exponential-time algorithm for the following problem: Given a simple closed curve $c$ on the boundary of a $3$-manifold $M$, is $c$ contractible in $M$? Then, I will describe an exponential-time algorithm to solve the same problem, removing the restriction for $c$ to be simple. The main tool for this result, obtained together with Salman Parsa, is the loop theorem, a fundamental tool in the study of $3$-manifolds, which I will also explain.
12 avril 2018
Pas de séminaire (séance commune avec le Séminaire de Combinatoire Philippe Flajolet)
24 mai 2018
14h Olivier Devillers Loria, Nancy
TBA
15h30 TBA
28 juin 2018
14h TBA
15h30 TBA

Le séminaire bénéficie du soutien de l'Institut Henri Poincaré.

Le comité scientifique est constitué de:

Le comité d'organisation est constitué de Steve Oudot, Arnau Padrol et Vincent Pilaud.