l'Ecole Normale Superieure
January 29, 2014
In the 90's numerical simulations have unveiled interesting properties of random ensembles of constraint satisfaction problems (satisfiability and graph coloring in particular). When a parameter of the ensemble (the density of constraints per variable) increases the probability of a satisfying instance drops abruptly from 1 to 0 in the large size limit. This threshold phenomenon has motivated a lot of research activity in theoretical computer science and in mathematics.