Communications |
Une courte liste d'exposés que j'ai présentés. Je n'ai pas ajouté les transparents des présentations car il vaut mieux lire les articles sur ma page «Publications».
- Diviser n'est pas régner ?
Présentation aux Journées Graphes et Algorithmes (J.G.A.) 2023, Université Lyon 1, 23 novembre 2023.
Résumé : Rappels et présentations de "nouveaux" résultats sur les décompositions obtenues grâce au principe de première différence, dont les décompositions en temps quasi-linéaire des graphes de degré borné. Contrairement à mon habitude, les transparents sont disponibles, car j'ai ajouté plusieurs idées en conclusion qui ne sont pas dans l'article. [.pdf] - Sur les représentations questionnables des ordres.
Séminaire de l'équipe MC2 (Modèles de Calcul et Complexité) du LIP (Laboratoire de l'Informatique du Parallélisme), ENS Lyon, 21 novembre 2019.
Résumé : Dans cet exposé, je présenterai des résultats à la fois sur les ordres et d'autres structures binaires comme les graphes qui ont comme point commun de pouvoir être décomposées selon le principe de première différence. Après avoir rappelé des résultats d'Hausdorff et de Sierpiński pour les ordres totaux, je présenterai des résultats structurels pour les ordres partiels facilement décomposables. Pour ces ordres, j'obtiens quelques résultats de complexité en temps polynomial pour le problème d'isomorphisme et un résultat partiel pour compter le nombre d'extensions linéaires (#P-complet). Puis, je généraliserai le principe de première différence dans une suite, à un principe des premières différences dans un arbre, afin d'obtenir une "largeur" de structure binaire associée à un nouveau type de décompositions hiérarchiques. Les décompositions hiérarchiques obtenues sont strictement plus puissantes que les décompositions arborescentes et de clique car elles permettent de décomposer les grilles, et sans doute tout graphe plongeable sur une surface. - Une classe d'ordres avec un algorithme de tri en temps "linéaire?".
Séminaire de l'équipe MC2 (Modèles de Calcul et Complexité) du LIP (Laboratoire de l'Informatique du Parallélisme), ENS Lyon, 4 octobre 2018.
Résumé : Pour le modèle de tri par comparaison, il n'est pas possible de faire mieux que la complexité en n log n. Néanmoins, si on regarde de plus près certains ordres, on peut obtenir une complexité en temps linéaire dans un modèle RAM avec coût unitaire sur les pointeurs et tailles. C'est l'objet de cet exposé de montrer que c'est le cas pour une vaste classe d'ordres qui comprend tous les ordres de l'informatique de gestion, notamment ceux des requêtes SQL, et probablement tous les ordres utilisés hors des laboratoires de recherche. - Graph covers and algebraic complexity.
Computational Complexity - Research Seminar, Saarland University, juillet 2008. -
On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth.
3rd International Computer Science Symposium in Russia (CSR 2008)
Moscou, Russie, du 7 au 12 juin 2008 ici. Deux photos ici et là. - Graph covers and algebraic complexity.
Exposé présenté au Workshop on Graph Decomposition: Theoretical, Algorithmic and Logical Aspects, CIRM-Marseille, avril 2008. - Couvertures de graphes et complexité algébrique.
Présentation effectuée aux Journées Graphes et Algorithmes 2007, Paris, novembre 2007. - Couvertures de graphes et complexité algébrique.
Séminaire de l'Équipe de Logique Mathématique de l'Université Paris 7 - Denis Diderot, novembre 2007. - Partitionnement d'hypergraphes.
Présentation effectuée aux Journées Graphes et Algorithmes 2006, Orléans, novembre 2006. - Partitionnement d'hypergraphes.
Réunion MAO, ENS Lyon, avril 2005.
