Phase transitions

In Statistical Physics phase transitions refer to non-analytical behavior of certain parameters characterizing the overall structure of a macroscopic system.

It turns that problems in Combinatorial Optimization often have phase transitions as well, and these phase transitions have implications for the computational difficulty of random instances of these problems. To find out more see the following introductive chapter of a book I co-edited.

- Determining the precise threshold behavior of various constraint satisfaction problems.
- Obtaining a precise characterization of constraint satisfaction problems whose threshold is sharp (coarse).
- Identifying the impact of phase transitions on the complexity of decision algorithms.