Graphes, Algorithmes et Probabilités – GAP

- Du local au global, la méthode de la cavité sur les graphes diluée. Nous allons étudier la mesure dans laquelle les propriétés globales d'un processus aléatoire défini sur un graphe sont déterminées par les propriétés locales des interactions sur ce graphe. À cette fin, nous allons relier la méthode de la cavité à l'analyse des zéros complexes de la fonction de partition, une approche qui vient aussi de la mécanique statistique. Cela nous permettra d'appliquer de nouvelles techniques pour l'étude des processus aléatoires sur de grands graphes dilués et de leurs matrices aléatoires associées .

- Optimisation combinatoire, algorithmes de réseau, inférence statistique et sciences sociales. Motivés par des problèmes d'optimisation combinatoire, nous allons attaquer des questions ouvertes en informatique théorique avec les nouveaux outils développés dans le premier projet. Ceci nous permettra de concevoir de nouveaux algorithmes distribués pour les réseaux de communication et de nouveaux algorithmes d'inférence dans les modèles graphiques. Nous analyserons également les réseaux d'un point de vue économique par l'étude de jeux sur des réseaux complexes.

www.di.ens.fr/~lelarge/anr/ANR-results.html

Nous pensons que les ambitieux travaux théoriques abordées par ce projet mèneront à l'élaboration de nouveaux outils dans le domaine de l'informatique, des réseaux et des sciences sociales, et à l'introduction de nouveaux paradigmes dans la théorie des probabilités.

www.di.ens.fr/~lelarge/anr/ANR-results.html

Au cours des dernières années, plusieurs domaines de recherche ont connu des progrès importants grâce à la collaboration fructueuse de mathématiciens, de physiciens théoriciens et chercheurs en informatique. L'un des fruits de cette collaboration est la méthode de la cavité. Née de la théorie des champs moyens des verres de spin, elle est essentielle pour comprendre la structure des mesures de Gibbs sur les graphes aléatoires dilués, qui jouent un rôle clé dans de nombreuses applications, allant de l'inférence statistique à l'optimisation, le codage et les sciences sociales.

L'objectif de ce projet est de développer des outils mathématiques afin de contribuer à une formalisation rigoureuse de la méthode de la cavité. Nous avons l'intention de lancer deux lignes de recherche nouvelles:
- Projet 1: Du local au global, la méthode de la cavité sur les graphes diluée. Nous allons étudier la mesure dans laquelle les propriétés globales d'un processus aléatoire défini sur un graphe sont déterminées par les propriétés locales des interactions sur ce graphe. À cette fin, nous allons relier la méthode de la cavité à l'analyse des zéros complexes de la fonction de partition, une approche qui vient aussi de la mécanique statistique. Cela nous permettra d'appliquer de nouvelles techniques pour l'étude des processus aléatoires sur de grands graphes dilués et de leurs matrices aléatoires associées .
-Projet 2: Optimisation combinatoire, algorithmes de réseau, inférence statistique et sciences sociales. Motivés par des problèmes d'optimisation combinatoire, nous allons attaquer des questions ouvertes en informatique théorique avec les nouveaux outils développés dans le projet 1. Ceci nous permettra de concevoir de nouveaux algorithmes distribués pour les réseaux de communication et de nouveaux algorithmes d'inférence dans les modèles graphiques. Nous analyserons également les réseaux d'un point de vue économique par l'étude de jeux sur des réseaux complexes.

Nous pensons que les ambitieux travaux théoriques abordées par ce projet mèneront à l'élaboration de nouveaux outils dans le domaine de l'informatique, des réseaux et des sciences sociales, et à l'introduction de nouveaux paradigmes dans la théorie des probabilités.