PhD graduated
Team : PolSys
Departure date : 12/31/2012

Supervision : Jean-Charles FAUGÈRE

Co-supervision : SAFEY EL DIN Mohab

Solving multihomogeneous and determinantal systems Algorithms - Complexity - Applications

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).

Defence : 10/09/2012 - 14h30 - Site Jussieu 25-26/105

Jury members :

Bern STURMFELS (Professeur, University of California, Berkeley) [Rapporteur]
Gilles VILLARD (Directeur de Recherche CNRS, École Normale Supérieure de Lyon) [Rapporteur]
Jean-Claude BAJARD (Professeur, Université Pierre et Marie Curie)
Jean-Charles FAUGÈRE (Directeur de Recherche INRIA, Centre Paris-Rocquencourt)
Antoine JOUX (Professeur associé, Université de Versailles Saint-Quentin-en-Yvelines)
Mohab SAFEY EL DIN (Professeur, Université Pierre et Marie Curie)
Bruno SALVY (Directeur de Recherche INRIA, École Normale Supérieure de Lyon)
Gilles VILLARD (Directeur de Recherche CNRS, École Normale Supérieure de Lyon)

2009-2016 Publications