Random constraint satisfaction problems: the statistical mechanics approach and results

Non-equilibrium Dynamics and Random Matrices
Topic:Random constraint satisfaction problems: the statistical mechanics approach and results
Speaker:Guilhem Semerjian
Affiliation:l'École Normale Supérieure
Date:Wednesday, January 29
Time/Room:2:00pm - 3:00pm/S-101
Video Link:https://video.ias.edu/nedrm/2014/0129-GuilhemSemerjian

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.