About

David Gamarnik is a Professor of Operations Research at the MIT Sloan School of Management. His research interests include discrete probability and random structures, algorithms and combinatorial optimization, statistics and machine learning, quantum computing and quantum information science, as well as stochastic processes and queueing theory. He received his B.A. in Mathematics from New York University in 1993 and his Ph.D. in Operations Research from MIT in 1998. Prior to joining MIT as a faculty member in 2005, he was a research staff member at IBM T. J. Watson Research Center from 1997 to 2005. Gamarnik is a fellow of the American Mathematical Society, the Institute for Operations Research and the Management Sciences, and the Institute for Mathematical Statistics. His notable contributions include co-authoring a textbook on queueing theory, serving as an area editor for the Mathematics of Operations Research journal, and delivering numerous lectures and tutorials on topics such as classical and quantum computing in random structures, the overlap gap property, and algorithmic hardness in random structures. He has received awards such as the Erlang Prize and the Best Publication Award from the Applied Probability Society of INFORMS, and has been recognized as a finalist in the Franz Edelman Prize competition of INFORMS.

Research topics

• Computer Science
• Mathematics
• Artificial Intelligence
• Algorithm
• Combinatorics
• Machine Learning
• Quantum mechanics
• Physics
• Theoretical computer science
• Mathematical optimization
• Discrete mathematics

Selected publications

• The free energy limit of the SYK model at high temperature

  arXiv (Cornell University) · 2026-05-04

  preprintOpen access1st authorCorresponding

  The Sachdev-Ye-Kitaev (SYK) model is a disordered quantum mean-field model studied in condensed matter physics and the holographic theory of black holes. Its structural properties can be derived heuristically using a combination of the replica method and path integration techniques. Analyzing it mathematically rigorously, however, turned out to be notoriously difficult, even for basic questions such as computing the annealed free energy. In this paper we rigorously compute the free energy limit (annealed and quenched) for this model at high enough but constant temperature. Our results are in numerical agreement with the results derived by physics methods. Remarkably, though, our method of proof is novel and is different from the physics approach. It is based on (a) the theory of the component structure of sparse random graphs and (b) a variant of the cavity method, used widely in prior rigorous and heuristic treatments of classical spin glasses.

  PublisherDOI

• The free energy limit of the SYK model at high temperature

  ArXiv.org · 2026-05-04

  articleOpen access1st authorCorresponding

  The Sachdev-Ye-Kitaev (SYK) model is a disordered quantum mean-field model studied in condensed matter physics and the holographic theory of black holes. Its structural properties can be derived heuristically using a combination of the replica method and path integration techniques. Analyzing it mathematically rigorously, however, turned out to be notoriously difficult, even for basic questions such as computing the annealed free energy. In this paper we rigorously compute the free energy limit (annealed and quenched) for this model at high enough but constant temperature. Our results are in numerical agreement with the results derived by physics methods. Remarkably, though, our method of proof is novel and is different from the physics approach. It is based on (a) the theory of the component structure of sparse random graphs and (b) a variant of the cavity method, used widely in prior rigorous and heuristic treatments of classical spin glasses.

  PublisherOA PDF

• Rigorous Asymptotics for First-Order Algorithms Through the Dynamical Cavity Method

  arXiv (Cornell University) · 2026-03-15

  preprintOpen access

  Dynamical Mean Field Theory (DMFT) provides an asymptotic description of the dynamics of macroscopic observables in certain disordered systems. Originally pioneered in the context of spin glasses by Sompolinsky and Zippelius (1982), it has since been used to derive asymptotic dynamical equations for a wide range of models in physics, high-dimensional statistics and machine learning. One of the main tools used by physicists to obtain these equations is the dynamical cavity method, which has remained largely non-rigorous. In contrast, existing mathematical formalizations have relied on alternative approaches, including Gaussian conditioning, large deviations over paths, or Fourier analysis. In this work, we formalize the dynamical cavity method and use it to give a new proof of the DMFT equations for General First Order Methods, a broad class of dynamics encompassing algorithms such as Gradient Descent and Approximate Message Passing.

  PublisherDOI

• Rigorous Asymptotics for First-Order Algorithms Through the Dynamical Cavity Method

  ArXiv.org · 2026-03-15

  articleOpen access

  Dynamical Mean Field Theory (DMFT) provides an asymptotic description of the dynamics of macroscopic observables in certain disordered systems. Originally pioneered in the context of spin glasses by Sompolinsky and Zippelius (1982), it has since been used to derive asymptotic dynamical equations for a wide range of models in physics, high-dimensional statistics and machine learning. One of the main tools used by physicists to obtain these equations is the dynamical cavity method, which has remained largely non-rigorous. In contrast, existing mathematical formalizations have relied on alternative approaches, including Gaussian conditioning, large deviations over paths, or Fourier analysis. In this work, we formalize the dynamical cavity method and use it to give a new proof of the DMFT equations for General First Order Methods, a broad class of dynamics encompassing algorithms such as Gradient Descent and Approximate Message Passing.

  PublisherOA PDF

• Sequential Dynamics in Ising Spin Glasses

  ArXiv.org · 2025-06-11

  preprintOpen access

  We present the first exact asymptotic characterization of sequential dynamics for a broad class of local update algorithms on the Sherrington-Kirkpatrick (SK) model with Ising spins. Focusing on dynamics implemented via systematic scan -- encompassing Glauber updates at any temperature -- we analyze the regime where the number of spin updates scales linearly with system size. Our main result provides a description of the spin-field trajectories as the unique solution to a system of integro-difference equations derived via Dynamical Mean Field Theory (DMFT) applied to a novel block approximation. This framework captures the time evolution of macroscopic observables such as energy and overlap, and is numerically tractable. Our equations serve as a discrete-spin sequential-update analogue of the celebrated Cugliandolo-Kurchan equations for spherical spin glasses, resolving a long-standing gap in the theory of Ising spin glass dynamics. Beyond their intrinsic theoretical interest, our results establish a foundation for analyzing a wide variety of asynchronous dynamics on the hypercube and offer new avenues for studying algorithmic limitations of local heuristics in disordered systems.

  PublisherOA PDFDOI

• Shattering in the Ising p-spin glass model

  Probability Theory and Related Fields · 2025-09-11 · 1 citations

  articleOpen access1st author

  Abstract We study the Ising p -spin glass model for large p . We show that for any inverse temperature $$\sqrt{\ln 2}&lt;\beta &lt;\sqrt{2\ln 2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msqrt> <mml:mrow> <mml:mo>ln</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msqrt> <mml:mo>&lt;</mml:mo> <mml:mi>β</mml:mi> <mml:mo>&lt;</mml:mo> <mml:msqrt> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>ln</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msqrt> </mml:mrow> </mml:math> and any large p , the model exhibits shattering : w.h.p. as $$n\rightarrow \infty $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi> </mml:mrow> </mml:math> , there exists exponentially many well-separated clusters such that (a) each cluster has exponentially small Gibbs mass, and (b) the clusters collectively contain all but a vanishing fraction of Gibbs mass. Moreover, these clusters consist of configurations with energy near $$\beta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>β</mml:mi> </mml:math> . Range of temperatures for which shattering occurs is within the replica symmetric region. To the best of our knowledge, this is the first shattering result regarding the Ising p -spin glass models. Furthermore, we show that for any $$\gamma &gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>γ</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> and any large enough p , the model exhibits an intricate geometrical property known as the multi Overlap Gap Property above the energy value $$\gamma \sqrt{2\ln 2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>γ</mml:mi> <mml:msqrt> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>ln</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msqrt> </mml:mrow> </mml:math> . Our proofs are elementary, and in particular based on simple applications of the first and the second moment methods.

  PublisherOA PDFDOI

• Optimal Hardness of Online Algorithms for Large Independent Sets

  arXiv (Cornell University) · 2025-04-15 · 1 citations

  preprintOpen access1st authorCorresponding

  We study the algorithmic problem of finding a large independent set in the Erd{ö}s-Rényi random graph $G(n,p)$. For constant $p$ and $b=1/(1-p)$, the largest independent set has size $2\log_b n$, while a simple greedy algorithm - revealing vertices sequentially and making decisions based only on previously seen vertices - finds an independent set of size $\log_b n$. In his seminal 1976 paper, Karp challenged to either improve this guarantee or establish its hardness. Decades later, this problem remains open - one of the most prominent algorithmic problems in the theory of random graphs. In this paper, we establish that a broad class of online algorithms fails to find an independent set of size $(1+ε)\log_b n$ whp. This class includes Karp's algorithm as a special case, and extends it by allowing the algorithm to query exceptional edges, not yet "seen" by the algorithm. Our lower bound holds for $p\in [d/n,1-n^{-1/d}]$. In the dense regime (constant $p$), we also prove that our result is asymptotically tight with respect to the number of exceptional edges queried, by designing an online algorithm which beats the half-optimality threshold when the number of exceptional edges slightly exceeds our bound. Our result provides evidence for the algorithmic hardness of Karp's problem, by supporting the conjectured optimality of the greedy algorithm and establishing it within the class of online algorithms. Our proof relies on a refined analysis of the geometric structure of large independent sets, establishing a variant of the Overlap Gap Property (OGP). While OGP has predominantly served as a barrier to stable algorithms, online algorithms are inherently unstable, necessitating new ideas. Our proof refines the OGP framework by incorporating several new ideas (including temporal interpolation paths and stopping-times) that we expect to be useful for other online models.

  PublisherOA PDFDOI

• Hardness of Sampling Solutions From the Symmetric Binary Perceptron

  Random Structures and Algorithms · 2025-07-01 · 2 citations

  articleOpen accessSenior author

  ABSTRACT 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 set of solutions to the symmetric binary perceptron model at any constraint‐to‐variable density. This result is in contrast to the question of finding a solution to the same problem, where efficient (and stable) algorithms are known to succeed at sufficiently low density. This result suggests that the solutions found efficiently—whenever this task is possible—must be highly atypical, and therefore provides an example of a problem where search is efficiently possible but approximate sampling from the set of solutions is not, at least within these two classes of algorithms.

  PublisherOA PDFDOI

• Decoded Quantum Interferometry Requires Structure

  ArXiv.org · 2025-09-18

  preprintOpen access

  We study the performance of Decoded Quantum Interferometry (DQI) on typical instances of MAX-$k$-XOR-SAT when the transpose of the constraint matrix is drawn from a standard ensemble of LDPC parity check matrices. We prove that if the decoding step of DQI corrects up to the folklore efficient decoding threshold for LDPC codes, then DQI is obstructed by a topological feature of the near-optimal space of solutions known as the overlap gap property (OGP). As the OGP is widely conjectured to exactly characterize the performance of state-of-the-art classical algorithms, this result suggests that DQI has no quantum advantage in optimizing unstructured MAX-$k$-XOR-SAT instances. We also give numerical evidence supporting this conjecture by showing that approximate message passing (AMP)--a classical algorithm conjectured to saturate the OGP threshold--outperforms DQI on a related ensemble of MAX-$k$-XOR-SAT instances. Finally, we prove that depth-$1$ QAOA outperforms DQI at sufficiently large $k$ under the same decoding threshold assumption. Our result follows by showing that DQI is approximately Lipschitz under the quantum Wasserstein metric over many standard ensembles of codes. We then prove that MAX-$k$-XOR-SAT exhibits both an OGP and a related topological obstruction known as the chaos property; this is the first known OGP threshold for MAX-$k$-XOR-SAT at fixed $k$, which may be of independent interest. Finally, we prove that both of these topological properties inhibit approximately Lipschitz algorithms such as DQI from optimizing MAX-$k$-XOR-SAT to large approximation ratio.

  PublisherOA PDFDOI

• Bounds on the Ground State Energy of Quantum p-Spin Hamiltonians

  Communications in Mathematical Physics · 2025-09-01 · 4 citations

  article
  PublisherDOI

Recent grants

• AF: Small: Low-Degree Methods for Optimization in Random Structures. Power and Limitations

  NSF · $531k · 2023–2026

• Statistical Physics Methods and Algorithmic Applications in Graphical Games and Combinatorial Optimization

  NSF · $337k · 2010–2013

• Inference in High-Dimensional Statistical Models: Algorithmic Tractability and Computational Barriers

  NSF · $200k · 2020–2023

• Stochastic Networks in the Heavy Traffic Regime: Algorithms, Approximations and Applications

  NSF · $245k · 2007–2010

• Local Algorithms for Random Networks: Power, Limitations and Applications

  NSF · $360k · 2013–2016

Frequent coauthors

• Eren C. Kızıldağ

  Columbia University

  21 shared

• Ilias Zadik

  New York University

  20 shared

• Devavrat Shah

  19 shared

• Prasad Tetali

  17 shared

• Dimitris Bertsimas

  16 shared

• David A. Goldberg

  Cornell University

  15 shared

• Dmitriy Katz

  15 shared

• Madhu Sudan

  Harvard University Press

  13 shared

Awards & honors

• Erlang Prize
• Best Publication Award from the Applied Probability Society…
• Fellow of the Institute for Mathematical Statistics (IMS) (2…
• INFORMS Fellow (2021)
• Fellow of the American Mathematical Society (AMS) (2022)