Graphs, Algorithms and Probability – GAP

From local to global, the cavity method on diluted graphs. We will study the extent to which the global properties of a random process defined on some graph are determined by the local properties of interactions on this graph. To this end, we will relate the cavity method to the analysis of the complex zeros of the partition function, an approach that also comes from statistical mechanics. This will allow us to apply new techniques to the study of random processes on large diluted graphs and associated random matrices.

Combinatorial optimization, network algorithms, statistical inference and social sciences. Motivated by combinatorial optimization problems, we will attack long-standing open questions in theoretical computer science with the new tools developed in the first project. We expect to design new distributed algorithms for communication networks and new algorithms for inference in graphical models. We will also analyze networks from an economic perspective by studying games on complex networks.

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

We believe that the ambitious theoretical work tackled by this project will lead to the development of novel, innovative tools in the field of computer science, networking and social sciences, and to the introduction of new paradigms in probability theory.

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

Over the last few years, several research areas have witnessed important progress through the fruitful collaboration of mathematicians, theoretical physicists and computer scientists. One of them is the cavity method. Originating from the theory of mean field spin glasses, it is key to understanding the structure of Gibbs measures on diluted random graphs, which play a key role in many applications, ranging from statistical inference to optimization, coding and social sciences.

The objective of this project is to develop mathematical tools in order to contribute to a rigorous formalization of the cavity method. We intend to launch two new research lines:
- Project 1: From local to global, the cavity method on diluted graphs. We will study the extent to which the global properties of a random process defined on some graph are determined by the local properties of interactions on this graph. To this end, we will relate the cavity method to the analysis of the complex zeros of the partition function, an approach that also comes from statistical mechanics. This will allow us to apply new techniques to the study of random processes on large diluted graphs and associated random matrices.
-Project 2: Combinatorial optimization, network algorithms, statistical inference and social sciences. Motivated by combinatorial optimization problems, we will attack long-standing open questions in theoretical computer science with the new tools developed in Project 1. We expect to design new distributed algorithms for communication networks and new algorithms for inference in graphical models. We will also analyze networks from an economic perspective by studying games on complex networks.

We believe that the ambitious theoretical work tackled by this project will lead to the development of novel, innovative tools in the field of computer science, networking and social sciences, and to the introduction of new paradigms in probability theory.