Groupe de Travail


Théorie du MinMax et Algorithmie géométrique

Organisé par

Matthieu Fradelizi-Xavier Goaoc-Laurent Hauswirth

Ce groupe de travail collaboratif se propose de réunir des chercheurs intéressés par la géométrie, l'analyse, l'algorithmique et la géométrie computationnelle autour des techniques de MinMax et des estimées de hauteur de passage du col ("Waist inequality").

Les séances auront lieu les mardi après-midi en Salle 3B082-Bâtiment Copernic-Marne-la-Vallée.

Programme :


  • mardi 14/03 à 15h40 : Clément Maria-"Breaking complexity barriers in low-dimensional topology "
Résumé: In this talk, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariants TV4,q, using the dimension of the first homology group of the 3-manifold as parameter. The computation of TV4,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 TV4,q.
  • mardi 07/03 de 16h30 à 18h00 : Xavier Goaoc-"A point in many simplices: the convex case"

  • mardi 20/02 de 16h30 à 18h00 : Alfredo Hubard-"Selection Lemma-A point in many triangles"
Résumé: We will survey several results around the selection lemma and the waist inequality. We will give a full proof of the selection lemma for affine maps.
  • mardi 31/01 de 16h30 à 18h00 : Xavier Goaoc-"Kakeya discret et méthode polynomiale en géométrie des incidences"
Résumé: Je présenterai d'abord une borne, due à Zeev Dvir, pour le problème de Kakeya dans les corps finis. La preuve a inspiré Larry Guth et Nets Katz, qui ont développé une méthode polynomiale" pour l'étude de problèmes d'incidence dans R^d ; j'en donnerai un ou deux exemples.
  • mardi 10/01 de 16h20 à 17h30 : Stéphane Sabourau-"Waist Theorem IV"

  • mardi 13/12 de 16h à 17h30 : Stéphane Sabourau-"Waist Theorem III"

  • mardi 29/11 de 16h à 17h30 : Stéphane Sabourau-"Waist Theorem II"

  • mardi 22/11 de 16h à 17h30 : Stéphabe Sabourau-"Waist Theorem I"

Ce groupe de travail est organisé dans le cadre du Labex Bézout-Géométrie discrète