Phase Transitions in Hard Optimization Problems
We study how the structure of the set of solutions evolves in each of these two problems as constraints are added. This allows us to determine the location of the threshold for both random satisfiability and random graph colorability up to second order terms. To do this we prove that for a large class of random constraint satisfaction problems the second moment of the number of solutions is captured by an "entropy-energy" tradeoff. Critical values of this tradeoff correspond to points where the structure of the space of solutions undergoes dramatic change. By identifying these critical points, we not only get to locate thresholds but we also gain rigorous insight on why algorithms have a hard time near them.
Based on joint works with Assaf Naor (Microsoft) and Yuval Peres (Berkeley).