3 papers
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…
quant-ph2024
Combinatorial NLTS From the Overlap Gap Property
Eric R. Anschuetz, David Gamarnik, Bobak Kiani
In an important recent development, Anshu, Breuckmann, and Nirkhe [ABN22] resolved positively the so-called No Low-Energy Trivial State (NLTS) conjecture by Freedman and Hastings.…