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 pilaud lix polytechnique fr.

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

15 mars 2018
14h Xavier Allamigeon CMAP, École Polytechnique
A formalization of convex polyhedra based on the simplex method
We present a formalization of convex polyhedra in the proof assistant Coq. The cornerstone of our work is a complete implementation of the simplex method, together with the proof of its correctness and termination. This allows us to define the basic predicates over polyhedra in an effective way (ie, as Coq programs), and relate them with the corresponding usual logical counterparts. The benefit of this approach is that we can easily derive the proof of several essential results on polyhedra, such as Farkas Lemma, duality theorem of linear programming, and Minkowski Theorem. The talk doesn't require any prior knowledge on theorem proving. This is joint work with Ricardo D. Katz (CIFACIS-CONICET, Argentina).
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:

• Éric Colin de Verdière (CNRS, LIGM, U. Paris-Est Marne-la-Vallée),
• Xavier Goaoc (LIGM, U. Paris-Est Marne-la-Vallée),
• Steve Oudot (Geometrica, Inria Saclay),
• Arnau Padrol (IMJ-PRG, Université Pierre et Marie Curie),
• Vincent Pilaud (CNRS, LIX, École Polytechnique).

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