Sébastien Tavenas face à la complexité algébrique
Chargé de recherche CNRS au Laboratoire d’analyse et de mathématiques appliquées (LAMA – CNRS/Université de Savoie Mont Blanc) pour la section 06, Sébastien Tavenas mène ses recherches au sein des équipes Logique, informatique et mathématiques discrètes et géométrie. Il travaille principalement sur la complexité des circuits arithmétiques, sujet sur lequel il a obtenu des résultats de tout premier plan mondial. Ces circuits diffèrent des circuits booléens classiques, qui manipulent des 0 ou des 1 à l’aide d’opérations booléennes, en utilisant des portes qui correspondent aux opérations arithmétiques d’addition et de multiplication. Sébastien Tavenas étudie la taille, minimale et maximale, des circuits qui résolvent différents problèmes. Très impliqué dans l’organisation de la recherche, il est également porteur d’un projet ANR JCJC et fait partie du comité scientifique du groupe de travail Complexité et algorithmes du Groupement de recherche Informatique fondamentale et ses mathématiques (GDR IFM).
Sébastien Tavenas a obtenu sa thèse en informatique en 2014 au Laboratoire de l'informatique du parallélisme (LIP – CNRS/ENS de Lyon/Université Claude Bernard) sur les bornes inférieures et supérieures dans les circuits arithmétiques. Il s’agit de savoir quels sont les nombres minimaux et maximaux d’opérations arithmétiques nécessaires pour qu’un algorithme résolve un problème donné. Le jeune chercheur a aussi passé deux postdoctorats, au Max Planck Institute à Sarrebruck (Allemagne) et à Microsoft Research à Bangalore (Inde). Il est recruté dans la foulée par le CNRS au LAMA en 2016.
« Quand on veut montrer qu’un problème est difficile, ma démarche est de ne pas mesurer le temps pour le résoudre mais le nombre d’opérations élémentaires qu’il faut effectuer, explique Sébastien Tavenas. La borne inférieure correspond au nombre minimal d’opérations nécessaires aux algorithmes pour résoudre le problème en question. »
« L’idée est de démontrer que certains problèmes sont difficiles à calculer. »
Avec des co-auteurs indiens, Sébastien Tavenas a obtenu les premières bornes inférieures superpolynomiales pour les circuits arithmétiques de profondeur constante, un résultat qui était attendu depuis une cinquantaine d’années. Ces travaux ont reçu le prix du meilleur article à la conférence Symposium on Foundations of Computer Science (FOCS) 2021 et ont entraîné une foule de nouvelles publications. Sébastien Tavenas est également expert en géométrie réelle creuse, c’est-à-dire l’étude de la géométrie du lieu des zéros des polynômes composés de très peu de monômes.
« Il serait très intéressant d’étendre les résultats sur la géométrie des polynômes creux à l’ensemble des polynômes faciles à calculer. »
« Je suis très content de cette récompense personnelle, mais mes travaux restent avant tout collectifs, affirme Sébastien Tavenas. Beaucoup de mes recherches sur la complexité algébrique viennent de collaborations nées de mon postdoctorat en Inde, pays où cette thématique est très présente. En comparaison, la thématique de la complexité algorithmique est assez peu représentée en France, j’espère que cette récompense aidera à donner de la visibilité à ces questions. »