Jennifer Chayes - Phase transitions in computer science: what makes hard problems hard

What makes hard problems hard? Understanding intractability is one of the fundamental problems in computer science. Even in the context of specific algorithms, it is often not obvious why certain problems are difficult. In this talk, I will discuss how concepts from physics, especially from the theory of phase transitions, allow us to understand the hardness of specific random algorithms, in particular Monte Carlo algorithms for certain magnetic models. I will also show how an insight into the phase structure of combinatorial models allows us to improve these algorithms. Finally, this analysis suggests why it may be so difficult to find substantially improved algorithms for certain problems in disordered systems. This is a new, cross-disciplinary approach to the study of algorithms and intractability. No prior knowledge of phase transitions, magnetic models, algorithms or intractability is assumed in this talk.