Maximally-stable Local Optima in Random Graphs and Spin Glasses: Phase Transitions and Universality

Yatin Dandi, David Gamarnik, Lenka Zdeborová

We consider $h$-stable local optima of Ising spin glass models, defined as spin configurations such that for nearly all of the spins, flipping their values results in increasing en…