153 citations · 1k across the 72 of their papers we have counts for
80 papers
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…
Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
David Gamarnik, Elchanan Mossel, Ilias Zadik
We show that sharp thresholds for Boolean functions directly imply average-case circuit lower bounds. More formally we show that any Boolean function exhibiting a sharp enough thre…
Shattering in the Ising Pure -Spin Model
David Gamarnik, Aukosh Jagannath, Eren C. Kızıldağ
We study the Ising pure -spin model for large . We investigate the landscape of the Hamiltonian of this model. We show that for any and any large enough , the model…
Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~\cite{schuetz2022combinatorial},\cite{angelini2023modern},\cite{schuetz2023reply}
David Gamarnik
Recently graph neural network (GNN) based algorithms were proposed to solve a variety of combinatorial optimization problems, including Maximum Cut problem, Maximum Independent Set…
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…
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.…