Agenda de l'ENS de Lyon

Le cadre général de cette thèse est l'étude des polynômes comme objet de modèles de calcul. Cette approche permet de définir de manière précise la complexité d'évaluation d'un polynôme, puis de classifier des familles de polynômes en fonction de leur difficulté dans ce modèle. Dans cette thèse, nous nous intéressons en particulier au modèle des sommes de puissance de forme linéaire, i.e. les polynômes qui s'écrivent  , avec  . Ce modèle semble assez naturel car il étends à la fois le modèle de Waring  et le modèle du shift creux  , mais peu de résultats sont connus pour cette généralisation.
Nous avons pu prouver des résultats structurels pour la version univarié de ce modèle, qui nous ont ensuite permis d'obtenir des bornes inférieures et des algorithmes de reconstruction, qui répondent au problème suivant : étant donné   par la liste de ses coefficients, retrouver les  qui apparaissent dans la décomposition optimale de  .
Nous avons aussi étudié plus en détails la version multivarié du modèle, qui avait été laissé ouverte par nos précédents algorithmes de reconstruction, et avons obtenu plusieurs résultats lorsque le nombre de termes dans une expression optimale est relativement petit devant le nombre de variables ou devant le degré du polynôme.