at the

American Institute of Mathematics, San Jose, California

organized by

Amir Dembo, Jian Ding, and Nike Sun

- 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 schedule.

A report on the workshop activities.

A list of open problems.

Papers arising from the workshop:

The Bousfield-Kuhn functor and Topological Andre-Quillen cohomology

by Mark Behrens and Charles Rezk

Comparing Dynamics: Deep Neural Networks versus Glassy Systems

by M. Baity-Jesi, L. Sagun, M. Geiger, S. Spigler, G. Ben Arous, C. Cammarota, Y. LeCun, M. Wyart, and G. Biroli

Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions

by Valentina Ros, Gerard Ben Arous, Giulio Biroli, and Chiara Cammarota

Spectral gap estimates in mean field spin glasses

by Gérard Ben Arous and Aukosh Jagannath

The landscape of the spiked tensor model

by Gerard Ben Arous, Song Mei, Andrea Montanari, and Mihai Nica

The satisfiability threshold for random linear equations

by Peter Ayre, Amin Coja-Oghlan, Pu Gao, and Noela Muller

The threshold for SDP-refutation of random regular NAE-3SAT

by Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, and Subhabrata Sen