Random constraint satisfaction problems: the statistical mechanics approach and results

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. In addition non-rigorous methods borrowed from theoretical physics (more precisely from mean-field spin glasses) have been applied to such problems, yielding a series of new results, including quantitative conjectures on the location of the satisfiability threshold, a much more detailed description of the structure of the satisfiable phase, and suggestion of new algorithmic strategies. Some of these insights have been later on turned into mathematically rigorous results. This seminar will attempt to give a non-technical review of these works at the interface between theoretical physics and mathematics.