Title: Shattering and Overlap Gap Property in Ising p-Spin Glass Model.
Abstract: We focus on the Ising p-spin glass model for large p. Confirming a celebrated prediction of Kirkpatrick and Thirumalai from 1987, we show the existence of a shattering phase: the configuration space breaks down into exponentially many well-separated clusters such that (a) each cluster has an exponentially small Gibbs mass, and (b) the clusters collectively contain all but a vanishing fraction of Gibbs mass. I will then discuss shattering in random computational problems (in particular, the random k-SAT) and the algorithmic implications of shattering.
In the second part of the talk, we focus on the algorithmic problem of optimizing the Hamiltonian of this model. We establish the presence of the multi Overlap Gap Property (m-OGP), an intricate geometrical property known to be a rigorous barrier for broad classes of algorithms. In particular, we show that (a) as p grows, the onset of the m-OGP asymptotically matches the algorithmic threshold of the Random Energy Model—the formal p->∞ limit of the p-spin model, and (b) the m-OGP exhibits a sharp phase transition. To the best of our knowledge, these are the first shattering results for Ising spin glasses and the first sharp phase transition results for the m-OGP.