salle A. Turing CE4
12 mai 2016 - 14h00
Factorisation de polynômes lacunaires
par Bruno Grenet de LIRMM, Université de Montpellier
Résumé : La représentation lacunaire est la représentation naturelle d'un polynôme par la liste de ses monômes non nuls (c'est essentiellement celle utilisée par le mathématicien sur sa feuille de papier). Elle est de taille logarithmique en le degré du polynôme, et donc compacte pour les polynômes de grand degré ayant peu de monômes non nuls. L'algorithmique des polynômes en représentation lacunaire est assez peu développée, en raison entre autres de la découverte dès les années 1970 de résultats de NP-difficulté pour des problèmes aussi simples que le calcul de PGCD. Néanmoins, des résultats plus récents ont démontré qu'il était possible d'effectuer certains calculs efficacement sous cette représentation.
Je présenterai dans mon exposé un panorama des (quelques) résultats et (nombreuses) questions ouvertes en algorithmique des polynômes lacunaires, en mettant l'accent sur les questions de factorisation.
