ANR Project GAP
Graphs, Algorithms and Probability
Back to the the project page
Proposal abstract
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:
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.