Bornes inférieures et algorithmes de reconstruction pour des sommes de puissances affines ; Lower bounds and reconstruction algorithms for sums of affine powers
You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Text;
Electronic Thesis;
E-Book
Title:
Bornes inférieures et algorithmes de reconstruction pour des sommes de puissances affines ; Lower bounds and reconstruction algorithms for sums of affine powers
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
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 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 AffPow des sommes de puissance de forme linéaire, i.e. les polynômes qui s'écrivent f = ∑_{i = 1}^s α_i ℓ_i^{e_i}, avec deg ℓ_i=1. Ce modèle semble assez naturel car il étend à la fois le modèle de Waring f = ∑ α_i ℓ_i^d et le modèle du décalage creux f = ∑ α_i ℓ^{e_i}, 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é f = ∑ α_i (x-a_i)^{e_i} par la liste de ses coefficients, retrouver les α_i, a_i, e_i qui apparaissent 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 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. ; The general framework of this thesis is the study of polynomials as objects of models of computation. This approach allows to define precisely the evaluation complexity of a polynomial, and then to classify families of polynomials depending 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 = ∑_{i = 1}^s α_i ℓ_i^{e_i}, with deg ℓ_i=1. This model is quite natural, as it extends both the Waring model f = ∑ α_i ℓ_i^d, and the sparsest shift model f = ∑ α_i ℓ^{e_i}, but it is still not well known. In this work, we obtained structural results for the univariate variant of ...