David Gamarnik
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
David Gamarnik has a total of 65 co-authors. Here are the top co-authors by number of shared publications:
- Aukosh Jagannath
Department of Statistics and Actuarial Science, Department of Applied Mathematics, University of Waterloo, Waterloo, Canada
8 shared publications - Dmitriy Katz
T.J. Watson Research Center IBM 10598 Yorktown Heights NY
7 shared publications - Devavrat Shah
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
4 shared publications - Eren C. Kızıldağ4 shared publications
- Ilias Zadik
Boston University
4 shared publications - Alexander S. Wein
University of California at Davis, Davis, USA
3 shared publications
Latest Publications
- 14 September 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- p. 1-33
Computing volume of a polytope and integrals in high dimensions deterministically
We design a Correlation-Decay based quasi-polynomial time deterministic approximation algorithm for computing high dimensional integrals, applied in two settings. The first is computing the volume of an independent set polytope with restrictions. Randomized polynomial time approximation algorithms for computing the volume of a convex body have been known now for several decades, but the corresponding deterministic counterparts are not available, and our algorithm is the first of this kind. The class of polytopes for which our algorithm applies arises as linear programming relaxation of the independent set problem with the additional restriction that each variable takes value in the interval left bracket 0 comma 1 minus alpha right bracket $[0,1-\alpha ]$ for some alpha less than 1 divided by 2 $\alpha \lt 1/2$ . (We note that the alpha greater than or equals 1 divided by 2 $\alpha \ge 1/2$ case is trivial). The method works provided alpha greater than 1 divided by 2 minus upper O left parenthesis 1 divided by normal upper Delta squared right parenthesis $\alpha \gt 1/2-O(1/\Delta ^2)$ , where normal upper Delta $\Delta$ is the maximum degree of the graph. When normal upper Delta equals 3 $\Delta =3$ (the sparsest non-trivial case), our method works provided 0.488 less than alpha less than 0.5 $0.488\lt \alpha \lt 0.5$ . Our second setting is to compute the integral of a multi-dimensional separable function, supported by some underlying hyper-graph structure, appropriately defined. Equivalently, our integral is the partition function of a graphical model with continuous potentials. For our method to work, we require that the domain is bounded and the hyper-edge potentials are positive and bounded on the domain. We further assume that the potentials have upper and lower bounds separated by a multiplicative factor of 1 plus upper O left parenthesis 1 divided by normal upper Delta squared right parenthesis $1 + O(1/\Delta ^2)$ , where normal upper Delta $\Delta$ is the maximum degree of the graph.- 14 September 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- p. 1-33
Computing volume of a polytope and integrals in high dimensions deterministically
We design a Correlation-Decay based quasi-polynomial time deterministic approximation algorithm for computing high dimensional integrals, applied in two settings. The first is computing the volume of an independent set polytope with restrictions. Randomized polynomial time approximation algorithms for computing the volume of a convex body have been known now for several decades, but the corresponding deterministic counterparts are not available, and our algorithm is the first of this kind. The class of polytopes for which our algorithm applies arises as linear programming relaxation of the independent set problem with the additional restriction that each variable takes value in the interval left bracket 0 comma 1 minus alpha right bracket $[0,1-\alpha ]$ for some alpha less than 1 divided by 2 $\alpha \lt 1/2$ . (We note that the alpha greater than or equals 1 divided by 2 $\alpha \ge 1/2$ case is trivial). The method works provided alpha greater than 1 divided by 2 minus upper O left parenthesis 1 divided by normal upper Delta squared right parenthesis $\alpha \gt 1/2-O(1/\Delta ^2)$ , where normal upper Delta $\Delta$ is the maximum degree of the graph. When normal upper Delta equals 3 $\Delta =3$ (the sparsest non-trivial case), our method works provided 0.488 less than alpha less than 0.5 $0.488\lt \alpha \lt 0.5$ . Our second setting is to compute the integral of a multi-dimensional separable function, supported by some underlying hyper-graph structure, appropriately defined. Equivalently, our integral is the partition function of a graphical model with continuous potentials. For our method to work, we require that the domain is bounded and the hyper-edge potentials are positive and bounded on the domain. We further assume that the potentials have upper and lower bounds separated by a multiplicative factor of 1 plus upper O left parenthesis 1 divided by normal upper Delta squared right parenthesis $1 + O(1/\Delta ^2)$ , where normal upper Delta $\Delta$ is the maximum degree of the graph.- Open Access
Minimum Number of Monochromatic Subgraphs of a Random Graph
We consider the problem of minimizing the number of monochromatic subgraphs of a random graph, when each node of the host graph is assigned one of the two colors. Using a recently discovered contiguity between appearance of strictly balanced subgraphs $F$ in a random graph, and random hypergraphs where copies of $F$ are generated independently, we show that the minimum value converges to a limit, when the expected number of copies of $F$ is linear in the number of nodes $|V|$. Furthermore, using the connections with mean field spin glass models, we obtain an asymptotic expression for this limit as the normalized expected number of copies of $F$ and the size of $F$ diverge to infinity.Open AccessMinimum Number of Monochromatic Subgraphs of a Random Graph
We consider the problem of minimizing the number of monochromatic subgraphs of a random graph, when each node of the host graph is assigned one of the two colors. Using a recently discovered contiguity between appearance of strictly balanced subgraphs $F$ in a random graph, and random hypergraphs where copies of $F$ are generated independently, we show that the minimum value converges to a limit, when the expected number of copies of $F$ is linear in the number of nodes $|V|$. Furthermore, using the connections with mean field spin glass models, we obtain an asymptotic expression for this limit as the normalized expected number of copies of $F$ and the size of $F$ diverge to infinity. - Open Access
Theoretical Compression Bounds for Wide Multilayer Perceptrons
Pruning and quantization techniques have been broadly successful in reducing the number of parameters needed for large neural networks, yet theoretical justification for their empirical success falls short. We consider a randomized greedy compression algorithm for pruning and quantization post-training and use it to rigorously show the existence of pruned/quantized subnetworks of multilayer perceptrons (MLPs) with competitive performance. We further extend our results to structured pruning of MLPs and convolutional neural networks (CNNs), thus providing a unified analysis of pruning in wide networks. Our results are free of data assumptions, and showcase a tradeoff between compressibility and network width. The algorithm we consider bears some similarities with Optimal Brain Damage (OBD) and can be viewed as a post-training randomized version of it. The theoretical results we derive bridge the gap between theory and application for pruning/quantization, and provide a justification for the empirical success of compression in wide multilayer perceptrons.
Open AccessTheoretical Compression Bounds for Wide Multilayer Perceptrons
Pruning and quantization techniques have been broadly successful in reducing the number of parameters needed for large neural networks, yet theoretical justification for their empirical success falls short. We consider a randomized greedy compression algorithm for pruning and quantization post-training and use it to rigorously show the existence of pruned/quantized subnetworks of multilayer perceptrons (MLPs) with competitive performance. We further extend our results to structured pruning of MLPs and convolutional neural networks (CNNs), thus providing a unified analysis of pruning in wide networks. Our results are free of data assumptions, and showcase a tradeoff between compressibility and network width. The algorithm we consider bears some similarities with Optimal Brain Damage (OBD) and can be viewed as a post-training randomized version of it. The theoretical results we derive bridge the gap between theory and application for pruning/quantization, and provide a justification for the empirical success of compression in wide multilayer perceptrons.
- Open Access
- 11 September 2025
- Published by Springer Nature in Probability Theory and Related Fields
- Vol. 193 (1-2) , 89-141
Shattering in the Ising p-spin glass model
We study the Ising p-spin glass model for large p. We show that for any inverse temperature $$\sqrt{\ln 2}<\beta <\sqrt{2\ln 2}$$ and any large p, the model exhibits shattering: w.h.p. as $$n\rightarrow \infty $$ , 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 $$ . 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 >0$$ 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}$$ . Our proofs are elementary, and in particular based on simple applications of the first and the second moment methods.- 11 September 2025
- Published by Springer Nature in Probability Theory and Related Fields
- Vol. 193 (1-2) , 89-141
Open AccessShattering in the Ising p-spin glass model
We study the Ising p-spin glass model for large p. We show that for any inverse temperature $$\sqrt{\ln 2}<\beta <\sqrt{2\ln 2}$$ and any large p, the model exhibits shattering: w.h.p. as $$n\rightarrow \infty $$ , 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 $$ . 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 >0$$ 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}$$ . Our proofs are elementary, and in particular based on simple applications of the first and the second moment methods. - Open Access
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
We consider the problem of recovering the support of a sparse signal using noisy projections. While extensive work has been done on the dense measurement matrix setting, the sparse setting remains less explored. In this work, we establish sufficient conditions on the sample size for successful sparse recovery using sparse measurement matrices. Bringing together our result with previously known necessary conditions, we discover that, in the regime where $ds/p \rightarrow +\infty$, sparse recovery in the sparse setting exhibits a phase transition at an information-theoretic threshold of $n_{\text{INF}}^{\text{SP}} = Θ\left(s\log\left(p/s\right)/\log\left(ds/p\right)\right)$, where $p$ denotes the signal dimension, $s$ the number of non-zero components of the signal, and $d$ the expected number of non-zero components per row of measurement. This expression makes the price of sparsity explicit: restricting each measurement to $d$ non-zeros inflates the required sample size by a factor of $\log{s}/\log\left(ds/p\right)$, revealing a precise trade-off between sampling complexity and measurement sparsity. Additionally, we examine the effect of sparsifying an originally dense measurement matrix on sparse signal recovery. We prove in the regime of $s = αp$ and $d = ψp$ with $α, ψ\in \left(0,1\right)$ and $ψ$ small that a sample of size $n^{\text{Sp-ified}}_{\text{INF}} = Θ\left(p / ψ^2\right)$ is sufficient for recovery, subject to a certain uniform integrability conjecture, the proof of which is work in progress.Open AccessThe Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
We consider the problem of recovering the support of a sparse signal using noisy projections. While extensive work has been done on the dense measurement matrix setting, the sparse setting remains less explored. In this work, we establish sufficient conditions on the sample size for successful sparse recovery using sparse measurement matrices. Bringing together our result with previously known necessary conditions, we discover that, in the regime where $ds/p \rightarrow +\infty$, sparse recovery in the sparse setting exhibits a phase transition at an information-theoretic threshold of $n_{\text{INF}}^{\text{SP}} = Θ\left(s\log\left(p/s\right)/\log\left(ds/p\right)\right)$, where $p$ denotes the signal dimension, $s$ the number of non-zero components of the signal, and $d$ the expected number of non-zero components per row of measurement. This expression makes the price of sparsity explicit: restricting each measurement to $d$ non-zeros inflates the required sample size by a factor of $\log{s}/\log\left(ds/p\right)$, revealing a precise trade-off between sampling complexity and measurement sparsity. Additionally, we examine the effect of sparsifying an originally dense measurement matrix on sparse signal recovery. We prove in the regime of $s = αp$ and $d = ψp$ with $α, ψ\in \left(0,1\right)$ and $ψ$ small that a sample of size $n^{\text{Sp-ified}}_{\text{INF}} = Θ\left(p / ψ^2\right)$ is sufficient for recovery, subject to a certain uniform integrability conjecture, the proof of which is work in progress. - 1 September 2025
- Published by Springer Nature in Communications in Mathematical Physics
- Vol. 406 (10) , 1-63
Bounds on the Ground State Energy of Quantum p-Spin Hamiltonians
- 1 September 2025
- Published by Springer Nature in Communications in Mathematical Physics
- Vol. 406 (10) , 1-63
Bounds on the Ground State Energy of Quantum p-Spin Hamiltonians
- Open Access
Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
We consider the problem of finding a dense submatrix of a matrix with i.i.d. Gaussian entries, where density is measured by average value. This problem arose from practical applications in biology and social sciences \cites{madeira-survey,shabalin2009finding} and is known to exhibit a computation-to-optimization gap between the optimal value and best values achievable by existing polynomial time algorithms. In this paper we consider the class of online algorithms, which includes the best known algorithm for this problem, and derive a tight approximation factor ${4\over 3\sqrt{2}}$ for this class. The result is established using a simple implementation of recently developed Branching-Overlap-Gap-Property \cite{huang2025tight}. We further extend our results to $(\mathbb R^n)^{\otimes p}$ tensors with i.i.d. Gaussian entries, for which the approximation factor is proven to be ${2\sqrt{p}/(1+p)}$.Open AccessFinding a dense submatrix of a random matrix. Sharp bounds for online algorithms
We consider the problem of finding a dense submatrix of a matrix with i.i.d. Gaussian entries, where density is measured by average value. This problem arose from practical applications in biology and social sciences \cites{madeira-survey,shabalin2009finding} and is known to exhibit a computation-to-optimization gap between the optimal value and best values achievable by existing polynomial time algorithms. In this paper we consider the class of online algorithms, which includes the best known algorithm for this problem, and derive a tight approximation factor ${4\over 3\sqrt{2}}$ for this class. The result is established using a simple implementation of recently developed Branching-Overlap-Gap-Property \cite{huang2025tight}. We further extend our results to $(\mathbb R^n)^{\otimes p}$ tensors with i.i.d. Gaussian entries, for which the approximation factor is proven to be ${2\sqrt{p}/(1+p)}$. - Open Access
Sequential Dynamics in Ising Spin Glasses
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.
Open AccessSequential Dynamics in Ising Spin Glasses
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.
- 8 May 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (2) , 1013-1081
Densest Subgraphs of a Dense Erdös–Rényi Graph. Asymptotics, Landscape, and Universality
We consider the problem of estimating the edge density of densest [Formula: see text]-node subgraphs of an Erdös–Rényi graph [Formula: see text]. The problem is well-understood in the regime [Formula: see text] and in the regime [Formula: see text]. In the former case it can be reduced to the problem of estimating the size of largest cliques, and its extensions [P. Balister, B. Bollobás, K. Gunderson, I. Leader, and M. Walters, Trans. Amer. Math. Soc., 370 (2018), pp. 7361–7389]. In the latter case the full answer is known up to the order [Formula: see text] using sophisticated methods from the theory of spin glasses. The intermediate case [Formula: see text], however, is not well studied and this is our focus. We establish that in this regime the density (that is the maximum number of edges supported by any [Formula: see text]-node subgraph) is [Formula: see text], w.h.p. as [Formula: see text], and provide more refined asymptotics under the [Formula: see text], for various ranges of [Formula: see text]. This extends earlier similar results in [D. Gamarnik and I. Zadik, The Landscape of the Planted Clique Problem: Dense Subgraphs and the Overlap Gap Property, preprint, https://arxiv.org/abs/1904.07174 , 2019] where this asymptotic was confirmed only when [Formula: see text] is a small constant. We extend our results to the case of “weighted” graphs, when the weights have either Gaussian or arbitrary sub-Gaussian distributions. The proofs are based on the second moment method combined with concentration bounds, the Borell-TIS inequality for the Gaussian case and the Talagrand’s inequality for the case of distributions with bounded support (including the [Formula: see text] case). The case of general distribution is treated using a novel symmetrized version of the Lindeberg argument, which reduces the general case to the Gaussian case. Finally, using the results above we conduct the landscape analysis of the related Hidden Clique Problem, and establish that it exhibits an overlap gap property when the size of the clique is [Formula: see text], confirming a hypothesis stated in [D. Gamarnik and I. Zadik, The Landscape of the Planted Clique Problem: Dense Subgraphs and the Overlap Gap Property, preprint, https://arxiv.org/abs/1904.07174 , 2019].
- 8 May 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (2) , 1013-1081
Densest Subgraphs of a Dense Erdös–Rényi Graph. Asymptotics, Landscape, and Universality
We consider the problem of estimating the edge density of densest [Formula: see text]-node subgraphs of an Erdös–Rényi graph [Formula: see text]. The problem is well-understood in the regime [Formula: see text] and in the regime [Formula: see text]. In the former case it can be reduced to the problem of estimating the size of largest cliques, and its extensions [P. Balister, B. Bollobás, K. Gunderson, I. Leader, and M. Walters, Trans. Amer. Math. Soc., 370 (2018), pp. 7361–7389]. In the latter case the full answer is known up to the order [Formula: see text] using sophisticated methods from the theory of spin glasses. The intermediate case [Formula: see text], however, is not well studied and this is our focus. We establish that in this regime the density (that is the maximum number of edges supported by any [Formula: see text]-node subgraph) is [Formula: see text], w.h.p. as [Formula: see text], and provide more refined asymptotics under the [Formula: see text], for various ranges of [Formula: see text]. This extends earlier similar results in [D. Gamarnik and I. Zadik, The Landscape of the Planted Clique Problem: Dense Subgraphs and the Overlap Gap Property, preprint, https://arxiv.org/abs/1904.07174 , 2019] where this asymptotic was confirmed only when [Formula: see text] is a small constant. We extend our results to the case of “weighted” graphs, when the weights have either Gaussian or arbitrary sub-Gaussian distributions. The proofs are based on the second moment method combined with concentration bounds, the Borell-TIS inequality for the Gaussian case and the Talagrand’s inequality for the case of distributions with bounded support (including the [Formula: see text] case). The case of general distribution is treated using a novel symmetrized version of the Lindeberg argument, which reduces the general case to the Gaussian case. Finally, using the results above we conduct the landscape analysis of the related Hidden Clique Problem, and establish that it exhibits an overlap gap property when the size of the clique is [Formula: see text], confirming a hypothesis stated in [D. Gamarnik and I. Zadik, The Landscape of the Planted Clique Problem: Dense Subgraphs and the Overlap Gap Property, preprint, https://arxiv.org/abs/1904.07174 , 2019].
- 1 February 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 50 (1) , 209-251
Stationary Points of a Shallow Neural Network with Quadratic Activations and the Global Optimality of the Gradient Descent Algorithm
We consider the problem of training a shallow neural network with quadratic activation functions and the generalization power of such trained networks. Assuming that the samples are generated by a full rank matrix [ ] of the hidden network node weights, we obtain the following results. We establish that all full-rank approximately stationary solutions of the risk minimization problem are also approximate global optimums of the risk (in-sample and population). As a consequence, we establish that, when trained on polynomially many samples, the gradient descent algorithm converges to the global optimum of the risk minimization problem regardless of the width of the network when it is initialized at some value [ ], which we compute. Furthermore, the network produced by the gradient descent has a near zero generalization error. Next, we establish that initializing the gradient descent algorithm below [ ] is easily achieved when the weights of the ground truth matrix [ ] are randomly generated and the matrix is sufficiently overparameterized. Finally, we identify a simple necessary and sufficient geometric condition on the size of the training set under which any global minimizer of the empirical risk has necessarily zero generalization error. Funding: The research of E. C. Kizildag is supported by Columbia University, with the Distinguished Postdoctoral Fellowship in Statistics. Support from the National Science Foundation [Grant DMS-2015517] is gratefully acknowledged.
- 1 February 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 50 (1) , 209-251
Stationary Points of a Shallow Neural Network with Quadratic Activations and the Global Optimality of the Gradient Descent Algorithm
We consider the problem of training a shallow neural network with quadratic activation functions and the generalization power of such trained networks. Assuming that the samples are generated by a full rank matrix [ ] of the hidden network node weights, we obtain the following results. We establish that all full-rank approximately stationary solutions of the risk minimization problem are also approximate global optimums of the risk (in-sample and population). As a consequence, we establish that, when trained on polynomially many samples, the gradient descent algorithm converges to the global optimum of the risk minimization problem regardless of the width of the network when it is initialized at some value [ ], which we compute. Furthermore, the network produced by the gradient descent has a near zero generalization error. Next, we establish that initializing the gradient descent algorithm below [ ] is easily achieved when the weights of the ground truth matrix [ ] are randomly generated and the matrix is sufficiently overparameterized. Finally, we identify a simple necessary and sufficient geometric condition on the size of the training set under which any global minimizer of the empirical risk has necessarily zero generalization error. Funding: The research of E. C. Kizildag is supported by Columbia University, with the Distinguished Postdoctoral Fellowship in Statistics. Support from the National Science Foundation [Grant DMS-2015517] is gratefully acknowledged.