Calcul Rapide de Relations Algébriques Multivariées – CREAM

La reconstruction de relations est une vaste famille de problèmes algorithmiques, allant de la résolution de systèmes linéaires présentant des motifs spécifiques, à des calculs de polynômes multivariés sous des contraintes d'approximation ou d'interpolation. Ces motifs et variables apportent une structure aux équations qui définissent les relations cherchées. La reconstruction de relations apparaît naturellement dans de nombreux domaines en informatique ; par exemple, en combinatoire, en cryptographie et en théorie des codes il est courant de reconstruire des relations algébriques entre des objets qui les définissent implicitement. De ce fait, la conception et l'implémentation d'algorithmes performants pour ce problème ont une grande importance et de larges impacts.

Ce projet allie une approche fondée sur la complexité, par le prisme des structures algébriques sous-jacentes à la reconstruction de relations, et le développement de représentations de données et techniques algorithmiques dédiées à ce problème. Il vise à concevoir la prochaine génération d'algorithmes de complexité quasi-optimale, à fournir des implémentations optimisées et libres, et à montrer l'impact des résultats en résolvant des défis provenant des domaines mentionnés ci-dessus.

Ce projet s'appuie sur des résultats récents qui ont permis de franchir des barrières de complexité vieilles de plusieurs décennies, pour certains types de relations. Il est organisé autour de trois objectifs principaux, dont deux vont apporter l'innovation algorithmique fondamentale, qui sera mise en oeuvre et exploitée dans le troisième pour résoudre des instances difficiles de reconstruction de relations.

Les innovations clés de ce projet sont des réductions efficaces à des sous-routines optimisées comme le produit de matrice et le produit de polynômes univariés, le réduction de dimension de l'espace où les relations sont cherchées, et l'exploitation de structures algébriques non-linéaires qui interviennent dans ce problème algorithmique.