Computational Phase Transitions

In a line of work going back to the 1980s, physicists have developed powerful heuristic methods to conjecture a rich phase diagram for randomized problems (specifically, for random constraint satisfaction problems): it is often the case that as some difficulty parameter is varied, the problem undergoes drastic structural changes (phase transitions) at critical values of the parameter. Some of the physics predictions are rigorously supported by recent work, but a robust mathematical theory remains lacking. In recent years there has also been a tremendous amount of progress in the study of computational transitions in average-case problems, notably in the so-called “sum-of-squares” framework. However, the existing body of work remains, for the most part, divided between a “structural properties” side (physicists and probabilists) and an “algorithmic” side (computer scientists). The rare instances of papers that transcend this divide have been highly influential. The goal of our workshop is to bring together these communities around topics of common interest to bridge the divide.

This workshop will now be held virtually. The workshop is being live streamed on our website. Full participation (including the capacity to ask questions) will be available via Zoom webinar. A link to the Zoom webinar will be shared with registrants closer to the event date. Please register by clicking the registration link above.