| Mathématiques discrètes |
Les mathématiques discrètes (par exemple la théorie des graphes, l'algèbre et la géométrie des structures finies) sont à l'oeuvre dans presque tous les domaines des mathématiques fondamentales. Souvent elles y sont mieux reçues sous cette forme un peu diffuse. La plupart des mathématiciens fondamentaux y ont recours dès qu'il se trouve quelque chose à classifier ou à ordonner. Il est un peu moins fréquent de les identifier comme un sujet de recherche distinct.
La situation est un peu différente en mathématiques appliquées et en informatique, où les mathématiques discrètes s'imposent plus naturellement comme un thème autonome : l'un des piliers de l'informatique fondamentale et le ressort d'un très grand nombre d'applications industrielles. Certains des grands problèmes issus des applications exercent alors sur ces mathématiques une pression assez violente pour faire émerger, à l'occasion, des idées nouvelles.
| Quelques nouvelles tendances |
Sans prétendre dresser une longue liste d'exemples, citons le travail de Cohn, Umans et al., sur la multiplication des matrices :
- Henry Cohn, Robert Kleinberg, Balazs Szegedy, Christopher Umans, Group-theoretic algorithms for matrix multiplication, Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23-25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379-388, lien,
Citons aussi les travaux d'Ajtai et al., qui montrent que la recherche du vecteur le plus court d'un réseau est un problème NP-dur et proposent des cryptosystèmes dont la sécurité repose sur de tels problèmes :
- Miklós Ajtai, The shortest vector problem in L2 is NP-hard for randomized reductions, Annual ACM Symposium on Theory of Computing, Dallas, Texas, United States, Pages: 10 - 19, 1998.
Un autre sujet récurrent est la recherche d'algorithmes optimaux ou quasi-optimaux pour résoudre les problèmes fondamentaux d'arithmétique des ordinateurs : multiplication, composition, factorisation des polynômes, avec en ligne de mire, une cryptographie asymétrique à la fois sûre et rapide.
- K.S. Kedlaya and C.~Umans, Modular composition in any characteristic, Foundations of Computer Science, FOCS, 2008.
Le séminaire permettra de se tenir informés des progrès constants réalisés dans ce domaine et de développer les échanges avec les principales équipes impliquées en France (projets INRIA TANC, LFANT et SECRET, équipe crypto de la DGA/CELAR par exemple).
Des objectifs réalistes sont : la construction et l'étude de nouveaux modèles performants pour les corps finis (bases normales de faible complexité, construction rapide de polynômes irréductibles); une meilleure compréhension des algorithmes quasi-optimaux (portée théorique, pertinence pratique) et , le cas échéant, leur mise en oeuvre pratique pour la réalisation de calcul records.
| Logique et sécurité |
Formellement, l'analyse de sécurité d'un système consiste à considérer un modèle de ce système, à munir un attaquant d'un ensemble de règles exprimant ses possibilités de déduction, et à étudier les propriétés du couple (modèle, système de déduction). Les travaux récents font le lien entre ce type d'analyse et les problèmes de déduction automatique, en particulier pour la logique du premier ordre (les ensembles de clauses) avec égalité. Le problème central de la déduction est de pouvoir décider, lorsque deux expressions sont présentées, si elles sont égales. On parle alors de problèmes d'unification (lorsqu'on recherche le domaine sur lequel les expressions sont égales) et d'unifiabilité (lorsqu'on recherche juste à savoir si deux expressions peuvent être égales). Plusieurs questions sur l'unification et l'unifiabilité sont intéressantes pour les mathématiciens et les informaticiens, telles que :
- Décrire les structures (groupes ou algèbres de termes modulo une théorie équationnelle) dans lesquels l'unifiabilité est décidable ou l'unification calculable
- Pour une instance particulière de théorie équationnelle, montrer la décidabilité de l'unifiabilité.
Un autre point d'intersection entre les mathématiques et la logique consiste à axiomatiser les propriétés des groupes utilisés en cryptographie, et de prouver la correction de cette axiomatisation par rapport à un modèle calculatoire. Nous pensons plus particulièrement à une axiomatisation par des théories du premier ordre avec égalités pour lesquelles il sera ensuite possible de fournir des procédures de décision.
| Théorie des graphes |
La théorie des graphes est présente un peu partout dans le projet MAELIA (Lien) et le projet de comparaison de graphes présenté sur ce lien. Avec le recrutement à l’IRIT d’Arnaud Pêcher, sur un poste de professeur, de nouvelles perspectives de collaboration sont désormais possibles.
De nouvelles perspectives de recherches sont possibles. On peut citer les travaux d'Ajtai et al., qui montrent que la recherche du vecteur le plus court d'un réseau est un problème NP-dur et proposent des cryptosystèmes dont la sécurité repose sur de tels problèmes :
- Miklós Ajtai, The shortest vector problem in L2 is NP-hard for randomized reductions, Annual ACM Symposium on Theory of Computing, Dallas, Texas, United States, Pages: 10 - 19, 1998.
Autour des isomorphismes de graphes, on peut signaler un problème crucial pour les logiciels de déduction automatique consiste à décider, étant données deux clauses C et C', si C et C' sont égales (modulo un renommage des variables). Ce problème, qui semble trivial à première vue, a en fait été montré comme ayant la même complexité que le problème d'isomorphisme de graphes (Basin, 1990). En pratique, des heuristiques sont implémentées pour tester si une clause déduite par résolution était déjà connue.
Comme indiqué en introduction de ce paragraphe, les compétences en théorie des graphes sont diffuses à l’IMT et il revient à FREMIT de les identifier pour faire émerger de nouvelles collaborations.