Orateur
Description
Constraint Satisfaction problems (CSPs) deal with finding a solution to a set of variables that satisfy a set of constraints. In the last decade, it has been found that many CSPs can have different levels of computational hardness when the number of constraints is changed. The same issue arises in inference problems in the so-called planted setting, where a planted configuration always exists by construction, and the number of constrains plays the role of a signal-to-noise ratio. In this presentation, I will focus on a particular model, namely the binary perceptron in the teacher-student scenario. In this system, it is known when it is easy or hard to find the teacher's solution, based on a statistical mechanics analysis of the landscape of solutions. Nevertheless, in practice, it remains very difficult to find the teacher's solutions in some parts of the easy region. We will show that by replicating the same system and adding a cooperative coupling between the different replicas, the phase diagram of the model is changed and it becomes much easier to find the teacher's solution using polynomial-time optimization algorithms based on MonteCarlo sampling, such as simulated annealing.
