Soutenance de thèse de Pierre-Jean Spaenlehauer

Bonjour à tous,

j'ai le plaisir de vous convier à ma soutenance de thèse, intitulée

Résolution de systèmes multi-homogènes et déterminantiels.

qui aura lieu

le mardi 9 octobre 2012 à 14h30
au LIP6 (Campus de Jussieu), salle 25-26-105,

après avis des rapporteurs
Bernd STURMFELS (Professeur, University of California, Berkeley)
Gilles VILLARD (Directeur de Recherche CNRS, École Normale
Supérieure de Lyon)

et devant le jury composé de
Jean-Claude BAJARD (Examinateur -- Professeur, Université Pierre
et Marie Curie)
Jean-Charles FAUGÈRE (Directeur -- Directeur de Recherche INRIA,
Centre Paris-Rocquencourt)
Antoine JOUX (Examinateur -- Professeur associé, Université de
Versailles Saint-Quentin-en-Yvelines)
Mohab SAFEY EL DIN (Directeur -- Professeur, Université Pierre
et Marie Curie)
Bruno SALVY (Examinateur -- Directeur de Recherche INRIA, École
Normale Supérieure de Lyon)
Gilles VILLARD (Rapporteur -- Directeur de Recherche CNRS, École
Normale Supérieure de Lyon)

Des plans d'accès au campus sont disponibles sur le site de l'UPMC
(http://www.upmc.fr/fr/universite/campus_et_sites/a_paris_et_en_idf/jussieu.html).
L'accès à la salle de soutenance se fera par le premier étage de la tour
26.

La soutenance sera suivie d'un pot auquel vous êtes cordialement invités.


Résumé [English version below]
-------------------------------------------
De nombreux systèmes polynomiaux multivariés apparaissant en Sciences
de l'Ingénieur possèdent une structure algébrique spécifique. En
particulier, les structures multi-homogènes, déterminantielles et les
systèmes booléens apparaissent dans une variété d'applications.
Une méthode classique pour résoudre des systèmes polynomiaux
passe par le calcul d'une base de Gröbner de l'idéal associé au
système.
Cette thèse présente de nouveaux outils pour la résolution de tels
systèmes structurés.

D'une part, ces outils permettent d'obtenir sous des hypothèses de
généricité des bornes de complexité du calcul de base de Gröbner
de plusieurs familles de systèmes polynomiaux structurés (systèmes
bilinéaires, systèmes déterminantiels, systèmes définissant des points
critiques, systèmes booléens). Ceci permet d'identifier des familles
de systèmes pour lequels la complexité arithmétique de résolution
est polynomiale en le nombre de solutions.

D'autre part, cette thèse propose de nouveaux algorithmes
qui exploitent ces structures algébriques pour améliorer
l'efficacité du calcul de base de Gröbner et de la résolution
(systèmes multi-homogènes, systèmes booléens). Ces résultats sont
illustrés par des applications concrètes en cryptologie (cryptanalyse
des systèmes MinRank et ASC), en optimisation et en géométrie réelle
effective (calcul de points critiques).


Abstract
------------
Multivariate polynomial systems arising in Engineering Science often carry
algebraic structures related to the problems they stem from. In
particular, multi-homogeneous, determinantal structures and boolean
systems can be met in a wide range of applications.
A classical method to solve polynomial systems is to compute a Gröbner
basis of
the ideal associated to the system. This thesis provides new tools for
solving such structured systems in the context of Gröbner basis algorithms.

On the one hand, these tools bring forth new bounds on the complexity of
the
computation of Gröbner bases of several families of structured systems
(bilinear systems, determinantal systems, critical point systems,
boolean systems). In particular, it allows the identification of
families of
systems for which the complexity of the computation is polynomial in
the number of solutions.

On the other hand, this thesis provides new algorithms which take
profit of these algebraic structures for improving the efficiency of
the Gröbner basis computation and of the whole solving process
(multi-homogeneous systems, boolean systems). These results are
illustrated by applications in cryptology (cryptanalysis of MinRank),
in optimization and in effective real geometry (critical point
systems).



Bien cordialement,
Pierre-Jean Spaenlehauer