Phase transitions in randomized computational problems
June 12 to June 16, 2017
American Institute of Mathematics,
San Jose, California
and Nike Sun
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:
- 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.
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.
- 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.