Jeudi 27 mars 2025, 14:00 à 15:00

salle de séminaire du département d'informatique

Alban Gilard

(LITIS, Université de Rouen-Normandie)

Le problème MinRank est un problème simple d'algèbre linéaire : étant donné des matrices avec des coefficients dans un corps, trouver une combinaison linéaire non triviale des matrices qui a un rang faible.
Il existe plusieurs modélisations algébriques du problème. Les principales sont : la modélisation de Kipnis-Shamir, la modélisation Minors et la modélisation des Support-Minors. La modélisation Minors a été bien étudiée ; nous pouvons analyser la complexité du calcul d'une base de Gröbner de la modélisation, par le biais du calcul de la série de Hilbert exacte pour une instance générique. Pour la modélisation Support-Minors, les premiers termes de la série de Hilbert étaient connus, basés sur un travail heuristique et expérimental.
Ici, nous fournissons une formule et une preuve pour la série de Hilbert complète de la modélisation Support-Minors pour des instances génériques. Cela est réalisé en adaptant des résultats bien connus sur les idéaux déterminantiels à un idéal généré par un sous-ensemble particulier de l'ensemble de tous les mineurs d'une matrice de variables. Nous montrons ensuite que cet idéal est généré par des monômes standards ayant une forme particulière, et nous dérivons la série de Hilbert en comptant le nombre de tels monômes standards.7
En suivant le travail réalisé pour la modélisation Minors, nous transférons ensuite les propriétés de cet idéal déterminantiel particulier aux idéaux générés par le système de Support-Minors, en ajoutant des formes génériques.
Ce travail permet de faire une comparaison précise entre les modélisations Minors et des Support-Minors, et d'estimer précisément la complexité de la résolution d'instances MinRank aléatoires.