Liens transverses ENS de Lyon

Agenda de l'ENS de Lyon

Bornes inférieures et algorithmes de reconstruction pour des sommes de puissances affines

Date
mer 11 juil 2018
Horaires

14h00

Lieu(x)

Amphi B

Intervenant(s)

Soutenance de thèse de M. Timothée PECATTE du LIP sous la direction de M. Pascal KOIRAN

Langue(s) des interventions

Description générale

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 Formule mathématiques 1 , avec Formule mathématiques 2 . Ce modèle semble assez naturel car il étends à la fois le modèle de Waring Formule mathématiques 3 et le modèle du shift creux Formule mathématiques 4 , 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é Formule mathématiques 5  par la liste de ses coefficients, retrouver les Formule mathématiques 6 qui apparaissent dans la décomposition optimale deFormule mathématiques 7  .
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.

 

Gratuit
Mots clés
Disciplines