Speakers

View Full Calendar

Probability Seminar

Event Type
Seminar/Symposium
Sponsor
Department of Mathematics
Location
36 English Building
Date
Dec 3, 2024   2:00 - 2:50 pm  
Speaker
Eren Kızıldağ (UIUC)
Contact
Xuan Wu
E-Mail
xuanw@illinois.edu
Views
22
Originating Calendar
Probability Research Area Calendar

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.

link for robots only