« Un lemme de voisinage dense : applications des classes de concepts partiels à la domination et au nombre chromatique » : l’article co-écrit par Romain Bourneuf, doctorant au LIPet au LaBRI (Bordeaux), Stéphan Thomassé, l’un de ses encadrants de thèse (LIP) et Pierre Charbit (IRIF, Université Paris Cité) vient d’être sélectionné par la célèbre conférence scientifique FOCS (Foundations of Computer Science).
C’est l’une des deux conférences les plus prestigieuses au monde en informatique théorique. La célèbre conférence scientifique FOCS, Foundations of Computer Science, vient de sélectionner l’article co-écrit par Romain Bourneuf, doctorant au LIP et au LaBRI (Bordeaux) , Stéphan Thomassé, l’un de ses encadrants de thèse (LIP) et Pierre Charbit (IRIF, Université Paris Cité).
« Avoir un article accepté par cette conférence signifie que des experts internationaux de tout premier plan ont reconnu notre travail comme à la fois original, rigoureux et porteur d’avancées importantes, commente Romain Bourneuf. Pour nous, c’est une très belle reconnaissance scientifique et aussi une grande source de motivation. »
Intitulé « Un lemme de voisinage dense : applications des classes de concepts partiels à la domination et au nombre chromatique », cet article explore un concept central de l’apprentissage automatique et ses applications dans un domaine apparemment très éloigné, la combinatoire, comme l’explique Romain Bourneuf dans le résumé de son article.
« La VC-dimension est un concept qui permet de mesurer en quelque sorte la “complexité” d’une famille d’objets mathématiques, comme des ensembles, des graphes ou des fonctions. Cette notion a été introduite dans le domaine de l’apprentissage pour estimer combien d’exemples sont nécessaires pour apprendre un modèle en intelligence artificielle.
Dans cet article, nous étudions une généralisation de cette notion et en approfondissons la compréhension théorique. Cela nous permet d’en tirer plusieurs applications dans des domaines différents de la combinatoire. Ainsi, d’une part, nous obtenons des preuves étonnamment simples de certains résultats déjà connus mais complexes, et d’autre part, nous établissons des résultats nouveaux. Par exemple, nous montrons qu’il est possible, dans n’importe quelle élection où les votants classent tous les candidats, de sélectionner un petit groupe de “vainqueurs” de sorte qu’aucun autre candidat ne soit largement préféré par rapport à tous les vainqueurs.
En conclusion, ce travail illustre comment des idées issues de l’apprentissage automatique peuvent être mises au service de problèmes en combinatoire, ouvrant de nouvelles perspectives de recherche. »
Référence de l’article : « A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number »
DOI : https://arxiv.org/abs/2504.02992
Disciplines
Mots clés