Workshops
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)

Because of COVID-19, we cannot schedule in-person events on the Berkeley campus through December 2020. This workshop will take place online. It will be open to the public for online participation. Please register to receive the zoom webinar access details.

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.

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