## Random constraint satisfaction problems: the statistical mechanics approach and results

Guilhem Semerjian

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.