Recherche

Doctorat (depuis septembre 2024)

Problèmes d'énumération et complexité descriptive
Université Paris Cité, Institut de Mathématique Jussieu-Paris Rive Gauche (IMJ-PRG),
Directeur: Arnaud Durand, Co-directeur: Yann Strozecki

Les problèmes algorithmiques les plus étudiés sont les problèmes de décision : pour une instance donnée, existe-t-il une solution ou non. De leur côté, les problèmes d'énumération s'intéressent à énumérer toutes les solutions. Contrairement aux problèmes de décision ou d'optimisation, où la complexité est généralement mesurée en la taille de l'instance du problème, les mesures de complexité en énumération doivent prendre en compte le nombre potentiellement exponentiel de solutions à énumérer. Pour cela, plusieurs classes de complexité « tractables » ont été introduites : temps output polynomial, temps incrémental polynomial, délai polynomial…
Cette thèse propose d'étudier la complexité descriptive des problèmes d'énumération, en cherchant des caractérisations logiques pour ces classes. Pour le temps output polynomial, cela consisterait à exhiber une logique L telle que pour tout problème P (de graphe par exemple) : P est exprimable dans L si et seulement si P est énumérable en temps output polynomial. De tels résultats peuvent être vus comme des méta-théorèmes algorithmiques, au sens où ils fournissent automatiquement un algorithme (que ce soit pour décider un problème, pour en générer une solution ou encore pour les énumérer toutes) à partir des expressions obtenues dans la logique.

Stages de recherche

Stage recherche de M2 (14 semaines : d'avril 2024 à juillet 2024)

Sémantique d'équipe et opérateur d'aplatissement
Université d'Helsinki (Finland), Département de Mathematique et Statistique,
Encadrants: Juha Kontinen, Jouko Väänänen et Arnaud Durand

La sémantique d'équipes (en anglais : team semantics) a été développée afin de décrire les concepts de dépendance et d'indépendance au moyen d'une logique formelle. Sur les formules de la logique du premier ordre, cette sémantique d'équipes constitue une extension de la sémantique classique, appelée sémantique de Tarski. On peut alors étudier de nombreux types de dépendances : dépendance, indépendance, inclusion, exclusion, etc. Le point de départ de ce stage a été l'introduction d'un opérateur F dit d'aplatissement (en anglais : flattening operator). La question naturelle qui suit l'ajout d'un tel opérateur à une certaine logique basée sur la sémantique d'équipe est de savoir à quel point le pouvoir d'expression de la logique a été augmenté. Dans un premier temps, le but a été de comprendre l'expressivité de quelques un de ces fragments, comme la logique de dépendance étendue avec F, la logique d'inclusion étendue avec F, etc. Une deuxième phase a été d'obtenir des translations vers des problèmes SAT, afin de comprendre la difficulté en terme cette fois-ci de complexité qu'apportait l'ajout de cet opérateur F.

Stage de recherche de M2 (20 semaines : de février 2023 à Juillet 2023)

Caractéristion logique des classes de complexité d'énumération
Université Paris-Diderot, Institut de Mathématique Jussieu-Paris Rive Gauche (IMJ-PRG),
Encadrant: Arnaud Durand

Les problèmes d'énumération sont des problèmes pour lesquels on souhaite énumérer toutes les solutions associées à une instance d'entrée. Pendant ce stage, on s'est intéressé à vouloir caractériser chacune des grandes classes de complexité d'énumération (OutputP, IncP et DelayP) via certaines logiques. Pour arriver à faire cela, on a dû développer des fragments de la logique du troisième ordre (principalement une logique existentielle de Horn du troisième ordre) pour d'abord réussir à capturer des problèmes centraux, comme le problème des ensembles indépendants maximaux (en anglais : maximal independent sets) ou encore le problème des couplage parfaits (en anglais : perfect matchings), et ensuite pouvoir s'attaquer aux classes de complexité d'énumération.

Stage de recherche de M1 (12 semaines : d'avril 2022 à juillet 2022)

Caractérisation de la localité de Hanf via une définissabilité élémentaire invariante
Université de Cambridge (Angleterre), Département d'informatique et de Technologie,
Encadrant: Anuj Dawar

La localité de Hanf est une manière d'exprimer le fait que des structures qui sont localement identiques ne peuvent être distinguées par des formules du premier ordre. Dans une publication de 2017, Lindell, Towsner et Weinstein ont montré qu'une classe de structures de degré borné est local au sens de Hanf (sous certaines conditions). Le but de ce stage a été d'étendre ce résultat à des classes de structures de degré non-borné, notamment en s'intéressant aux structures de largeur arborescente bornée (en anglais : bounded tree-width).

Stage de recherche de L3 (6 semaines : de mai 2021 à juillet 2021)

Automates cellulaires unilatères et indécidabilité
Université d'Orléans (France), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), équipe GAMoC,
Encadrants: Martin Delacourt et Nicolas Ollinger

Le problème de la périodicité des automates cellulaires est connu pour être indécidable dans le cas général. Il a été montré que même si l'on se restreignait au cas de la dimension 1, le problème restait indécidable. Cependant, le problème est encore ouvert pour le cas des automates cellulaires unilatères, autrement dit des automates cellulaires 1D qui ne peuvent « voir » que d'un côté seulement. Pendant ce stage, on s'est intéressé à la préservation du caractère périodique des automates cellulaires unilatères sous une certaine transformation : le plongement.