Phase transitions in randomized computational problems

Original Announcement

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

The workshop schedule.

A report on the workshop activities.

A list of open problems.

Papers arising from the workshop: