Showing math.PRShow all
2 papers · 1 filter
math.PR2025
Maximally-stable Local Optima in Random Graphs and Spin Glasses: Phase Transitions and Universality
Yatin Dandi, David Gamarnik, Lenka Zdeborová
We consider -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…
math.PR2025
Hardness of sampling solutions from the Symmetric Binary Perceptron
Ahmed El Alaoui, David Gamarnik
We show that two related classes of algorithms, stable algorithms and Boolean circuits with bounded depth, cannot produce an approximate sample from the uniform measure over the se…