Laboratoire de Physique Théorique
Toulouse - UMR 5152

In the first part of this talk I will present a study of the typical complexity of Constraint Satisfaction Problems. The typical complexity of Constraint Satisfaction Problems (CSP) can be studied using random ensembles of instances. One observes threshold phenomena when the density of constraints increases, in particular a clustering phase transition at which typical solutions shatter into disconnected components. We will introduce a bias that breaks the uniformity among solutions of a given instance of CSP, and look at the evolution of the clustering threshold under this bias, focusing on the bicoloring of $k$-uniform random hypergraphs. For small values of $k$, we show that this bias can delay the clustering transition to higher densities of constraints, and that it has a positive impact on the performances of Simulated Annealing algorithm to find a solution for a given instance of the bicoloring problem. In the large $k$ limit, we compute the asymptotic expansion of the clustering threshold for the uniform and the biased measure, and characterize the gain obtained with our implementation of the bias.

In the second part of this talk, I will propose to study multiple interacting spreading processes on graphs. The interaction between these processes can be of a competitive or a collaborative nature. They can be used to model the battle on public opinion and competitive marketing campaign, or the joint spread of multiple diseases in a population of individuals. We will look at several quantities that allows to study how the diffusion of a given spreading process is affected by its interaction with other spreading processes.