for this workshop
Phase transitions in randomized computational problems
American Institute of Mathematics, San Jose, California
Amir Dembo, Jian Ding, and Nike Sun
This workshop, sponsored by AIM and the NSF, 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.
The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.
The deadline to apply for support to participate in this workshop has passed.
For more information email firstname.lastname@example.org