Phase transitions in randomized computational problems

June 12 to June 16, 2017

at the

American Institute of Mathematics, San Jose, California

organized by

Amir Dembo, Jian Ding, and Nike Sun

Original Announcement

This workshop will be devoted to the study of random constraint satisfaction problems (CSPs), with an emphasis on threshold phenomena and related algorithmic challenges. Heuristic methods of statistical physics predict a rich phase diagram for many problems of this type. In recent years, building on the physics insight, some of these predictions have been rigorously proved. Our aim is to make further progress in these directions, focusing on the following topics:
  1. Solution geometry. The solution space of a random CSP is a random subset of the space of all possible variable assignments. There are many interesting open questions concerning the typical geometric properties of this space. For example, a large class of sparse random CSPs (k-SAT, coloring, independent set) is expected to exhibit "one-step replica symmetry breaking" (1RSB) -- in a certain regime, it is conjectured that the solution space consists (mostly) of a large bounded number of connected components, with relative weights distributed as a Poisson--Dirichlet process. Some manifestations of this prediction have been proved in recent years, but the Poisson--Dirichlet picture remains an interesting open question.
  2. Full RSB in sparse graphs. For some well-known models, the solution geometry is believed to be much more complicated than 1RSB. For example, the MAX-CUT problem on sparse random graphs is believed to exhibit full RSB (infinitely many levels of replica symmetry breaking). In comparison there is a relatively full understanding of the Sherrington--Kirkpatrick model, which also exhibits full RSB but in the setting of dense graphs. In the sparse setting there has been some recent progress, but many fundamental questions remain open.
  3. Algorithmic challenges. It is conjectured that the geometry of the solution space is related to algorithmic challenges. The sum-of-squares hierarchy provides one possible framework for studying this question, for example, in the context of the planted clique problem. SDP methods further exhibit phase transitions which are interesting in their own right.

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.

A list of open problems.