Click here to load reader

Bornes inférieures et algorithmes de reconstruction perso.ens-lyon.fr/ 2 Titre : Bornes inférieures et algorithmes de reconstruction pour des sommes de puissances affines Résumé

  • View
    0

  • Download
    0

Embed Size (px)

Text of Bornes inférieures et algorithmes de reconstruction perso.ens-lyon.fr/ 2 Titre : Bornes...

  • No d’ordre NNT : 2018LYSEN029

    THÈSE DE DOCTORAT DE L’UNIVERSITÉ DE LYON opérée par

    l’École Normale Supérieure de Lyon

    École Doctorale N◦512 École Doctorale en Informatique et Mathématiques de Lyon

    Discipline : Informatique

    Soutenue publiquement le 11/07/2018, par : Timothée PECATTE

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

    puissances affines

    Devant le jury composé de :

    Markus BLÄSER, Universität des Saarlandes Rapporteur Alin BOSTAN, INRIA Saclay Île-de-France Rapporteur Evelyne HUBERT, INRIA Méditerranée Examinatrice Claire MATHIEU, CNRS Examinatrice Bruno SALVY, INRIA Examinateur

    Pascal KOIRAN, École normale supérieure de Lyon Directeur de thèse

  • 2

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

    Résumé : Le cadre général de cette thèse est l’étude des polynômes comme objets de modèles de calcul. Cette approche permet de définir de manière précise la com- plexité 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 AffPow des sommes de puissance de forme linéaire, i.e. les polynômes qui s’écrivent f =

    ∑s i=1 αi`

    ei i , avec deg `i = 1. Ce modèle semble

    assez naturel car il étend à la fois le modèle de Waring f = ∑ αi`

    d i et le mod-

    èle du décalage creux f = ∑ αi`

    ei , mais peu de résultats sont connus pour cette généralisation. Nous avons pu prouver des résultats structurels pour la version uni- varié 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é f =

    ∑ αi(x − ai)ei par la liste de ses coefficients, retrouver les αi, ai, ei qui appa-

    raissent dans la décomposition optimale de f . Nous avons aussi étudié plus en détails la version multivarié du modèle, qui avait été laissé ouverte par nos précédents al- gorithmes 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.

    Mots-clés : complexité algébrique, théorie de Valiant, bornes inférieures, indépen- dance linéaire, algorithmes de reconstruction, problème de Waring, décalage creux.

  • 3

    Title : Lower bounds and reconstruction algorithms for sums of affine powers

    Abstract : The general framework of this thesis is the study of polynomials as objects of models of computation. This approach allows to define precisely the com- plexity of evaluating a polynomial, and then to classify families of polynomials de- pending on their complexity. In this thesis, we focus on the study of the model of sums of affine powers, that is polynomials that can be written as f =

    ∑s i=1 αi`

    ei i ,

    with deg `i = 1. This model is quite natural, as it extends both the Waring model f =

    ∑ αi`

    d i , and the sparsest shift model f =

    ∑ αi`

    ei , but it is still not well known for this extension. In this work, we obtained structural results for the uni- variate variant of this model, which allow us to obtain both lower bounds and recon- struction algorithms. These algorithms aim to solve the following problem: given f =

    ∑ αi(x − ai)ei as a list of its coefficient, find the values of the αi’s, ei’s and

    ai’s of an optimal decomposition of f . We also studied the multivariate case and obtained several reconstruction algorithms that work whenever the number of terms in the optimal expression is small in terms of the number of variable or the degree of the polynomial.

    Keywords : algebraic complexity, Valiant’s theory, lower bounds, linear indepen- dence, reconstruction algorithm, Waring problem, sparsest shift.

  • 4

  • Remerciements

    TROIS ANNÉES DE TRAVAIL, résumées en un manuscrit de 120 pages qui a étéscrupuleusement relu par Markus BLÄSER et Alin BOSTAN, mes deux rap- porteurs. Je tiens à les remercier chaleureusement pour leurs retours instructifs, et pour leurs suggestions qui ouvrent des perspectives intéressantes à étudier dans le futur. Je suis également reconnaissant envers Evelyne HUBERT, Claire MATHIEU et Bruno SALVY pour avoir accepté de prendre part à mon jury de soutenance. Pou- voir m’entourer de spécialistes couvrant un large spectre de l’informatique théorique pour ma soutenance est un privilège. Pascal, un grand merci pour ces trois ans d’encadrement, pendant lesquels j’ai beaucoup appris. Tu as su te rendre disponible lorsque j’en avais besoin et me laisser de nombreuses libertés pour que j’explore la science seul, et je t’en suis reconnaissant. Natacha, même si tu n’es pas officielle- ment co-encadrante pour des raisons administratives , merci à toi aussi pour ton soutien, tes conseils (scientifiques et gastronomiques), et pour m’avoir fait découvrir le monde merveilleux de la diffusion scientifique. Je souhaite à tous les thésards de bénéficier d’un tel encadrement.

    HORDE ERRANTE entre le LIP et le LUG, l’équipe MC2 est devenue ma secondefamille durant ces années de thèses. Merci donc à Nathalie pour être toujours disponible pour parler de vulgarisation et pour tes magnifiques jeux de tuiles en tout genre; à Omar pour les TDs très instructifs de théorie de l’information; à Michael pour les bidouilles électroniques et impressions 3D; à Éric pour les concours de pro- grammation effective; à Stéphan pour tes questions impossibles et tes preuves avec les mains; et à Nicolas pour ses anecdotes et la découverte de la chanson française. Je pense aussi aux membres non-permanents que j’ai pu côtoyé durant ma thèse : merci à Sebastián d’être aussi fou et d’aimer autant les lamas; à Nam de dire toujours “Ok” même quand tu ne comprends pas ce qu’on te dit; à Matthieu pour la truffe, les mo- ments de détente, et ton lot d’inepties quotidiennes (le LIP est trop calme sans elles); à Étienne pour cette cohabitation sympathique, bien que trop courte et très lacunaire; à Alexandre pour ton humour étrange; à William pour tes bouteilles d’eau gazeuses

  • Remerciements ii

    et tes propos fachos. Je tiens aussi à remercier les différentes personnes avec qui j’ai eu la chance de travailler pendant cette thèse. Merci donc à N. Kayal et C. Saha pour les discussions et les échanges instructifs sur notre article commun (ICALP 2015), article qui fut à l’origine de cette thèse. Un ÉNORME merci à Nacho pour ces heures indénombrables de discussions et de travail ensemble, pour tes “Ok!”, tes “eslides” et ton amour du football (> aux échecs car continu). Travailler avec toi fut une expérience stimulante et enrichissante, et j’espère que mes “ça marche pas” ne te décourageront pas de collaborer de nouveau avec moi par la suite.

    AUCUN EXPOSÉ DE CONFÉRENCE n’aurait pu être réalisé sans l’aide des assis-tantes administratives du LIP pour préparer les missions. Un grand merci donc à Marie, Chiraz, Pauline, Danièle et Kadiatou pour m’avoir aidé et pour avoir répondu à mes nombreuses questions et demandes. Avant de commencer ma thèse, j’ai eu le plaisir de découvrir l’informatique théorique au département informatique de l’ÉNS de Lyon. Pour tout ce qu’ils m’ont appris, je souhaite remercier mes en- seignants : Eric (x2), Daniel, Alexandre, Guillaume, Florent, Pascal, Stéphan, Nat- acha, . . . Pour m’avoir supporté au quotidien, avec mon opiniâtreté et mon orgueil, un grand merci à mes camarades : Fred, Matthieu, Thomas, Quentin, Antoine (#projet), Benjamin, Henri, Bertrand, William, . . . Je tiens aussi à remercier Lucas, initiale- ment mon compagnon d’agrégation, et maintenant un collaborateur sur de nombreux projets intéressant.

    N’AYANT PAS PEUR DE L’AVENTURE, j’ai signé en deuxième année pour une Ac-tivité Complémentaire de Diffusion, sans trop savoir à quoi m’attendre. Ce fut une magnifique expérience, enrichissante et passionnante, durant laquelle j’ai ren- contré plusieurs personnes formidables, soucieuses de partager leur amour pour les sciences au plus grand nombre. Un grand merci donc à toutes les sympathisants de la Maison des Mathématiques et de l’Informatique : Jean-Baptiste, Natacha, Nathalie, Aline, Éric, Alix, Léa, Carine, Séverine, Régis, Christian; ainsi qu’au groupe ISO et à Yves.

    KYRIELLE DE MOMENTS furent passés en dehors du laboratoire durant cette thèse.Merci donc aux PhDiscs pour les tournois, rendez-vous biannuels imman- quables, pendant lesquels la cuisine, les jeux de société, et l’asociabilisation sont aussi important que le jeu sur les terrains. Merci également aux membres du GDJA, pour toutes les soirées, sorties et autres moments fraternels si précieux. Parce que je ne suis pas tombé dans l’informatique par hasard, je remercie mes parents de m’avoir initié à ce merveilleux monde dès mon plus jeune âge, et pour m’avoir toujours sup- porté dans cette voie. Et parce qu’ils ne m’ont pas demandé si souvent que cela à quoi servait ma thèse, je remercie mes frères et sœurs, mes beaux-parents et le reste de ma famille.

    SANS VOUS DEUX, je ne serais rien. Merci Mélody pour ton support incondition-nel durant ces trois années, pleines d’aventures, d’incertitudes et de découvertes. Merci à toi Éloan de partager ta joie de viv

Search related