Fall 2020

Computational Phase Transitions

Sep. 21Sep. 25, 2020

Add to Calendar

Organizers: Cris Moore (Santa Fe Institute; co-chair), Ryan O'Donnell (Carnegie Mellon University; co-chair), David Gamarnik (MIT), Andrea Montanari (Stanford University), Lenka Zdeborová (CNRS and CEA Saclay)

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.

All events take place in the Calvin Lab auditorium.

Further details about this workshop will be posted in due course. Enquiries may be sent to the organizers workshop-hd1 [at] (at this address).