David Gamarnik

ORCID

Publication Activity (10 Years)

Years Active: 1996-2024
Publications (10 Years): 54

Top Venues

CoRR

Random Struct. Algorithms

ISIT

Math. Oper. Res.

Publications

David Gamarnik, Devin Smedira
Integrating High-Dimensional Functions Deterministically. CoRR (2024)
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics. SIAM J. Comput. 53 (1) (2024)
Ahmed El Alaoui, David Gamarnik
Hardness of sampling solutions from the Symmetric Binary Perceptron. CoRR (2024)
David Gamarnik, Elchanan Mossel, Ilias Zadik
Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique. CoRR (2023)
David Gamarnik, Devin Smedira
Computing the Volume of a Restricted Independent Set Polytope Deterministically. CoRR (2023)
David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu
Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization. COLT (2023)
David Gamarnik
Correlation decay and the absence of zeros property of partition functions. Random Struct. Algorithms 62 (1) (2023)
David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu
Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization. CoRR (2023)
David Gamarnik
Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~\cite{schuetz2022combinatorial}, \cite{angelini2023modern}, \cite{schuetz2023reply}. CoRR (2023)
David Gamarnik, Mihyun Kang, Pawel Pralat
Cliques, Chromatic Number, and Independent Sets in the Semi-random Process. CoRR (2023)
David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu
Algorithms and Barriers in the Symmetric Binary Perceptron Model. CoRR (2022)
David Gamarnik, Eren C. Kizildag, Ilias Zadik
Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks. IEEE Trans. Signal Process. 70 (2022)
Joao Basso, David Gamarnik, Song Mei, Leo Zhou
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. CoRR (2022)
David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu
Algorithms and Barriers in the Symmetric Binary Perceptron Model. FOCS (2022)
David Gamarnik, John N. Tsitsiklis, Martin Zubeldia
Stability, Memory, and Messaging Trade-Offs in Heterogeneous Service Systems. Math. Oper. Res. 47 (3) (2022)
David Gamarnik, Eren C. Kizildag
The Random Number Partitioning Problem: Overlap Gap Property and Algorithmic Barriers. ISIT (2022)
David Gamarnik, Cristopher Moore, Lenka Zdeborová
Disordered Systems Insights on Computational Hardness. CoRR (2022)
Joao Basso, David Gamarnik, Song Mei, Leo Zhou
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. FOCS (2022)
David Gamarnik, Eren C. Kizildag, Ilias Zadik
Self-Regularity of Output Weights for Overparameterized Two-Layer Neural Networks. ISIT (2021)
David Gamarnik
The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures. CoRR (2021)
David Gamarnik, Eren C. Kizildag, Ilias Zadik
Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks. CoRR (2021)
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
Circuit Lower Bounds for the p-Spin Optimization Problem. CoRR (2021)
David Gamarnik, Eren C. Kizildag, Ilias Zadik
Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection. IEEE Trans. Inf. Theory 67 (12) (2021)
Matt Emschwiller, David Gamarnik, Eren C. Kizildag, Ilias Zadik
Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena. CoRR (2020)
David Gamarnik, Eren C. Kizildag
Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average. ISIT (2020)
David Gamarnik, John N. Tsitsiklis, Martin Zubeldia
Stability, memory, and messaging tradeoffs in heterogeneous service systems. CoRR (2020)
David Gamarnik
Correlation Decay and the Absence of Zeros Property of Partition Functions. CoRR (2020)
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
Low-Degree Hardness of Random Optimization Problems. CoRR (2020)
Uriel Feige, David Gamarnik, Joe Neeman, Miklós Z. Rácz, Prasad Tetali
Finding cliques using few probes. Random Struct. Algorithms 56 (1) (2020)
Edward Farhi, David Gamarnik, Sam Gutmann
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case. CoRR (2020)
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
Low-Degree Hardness of Random Optimization Problems. FOCS (2020)
David Gamarnik, Eren C. Kizildag, Ilias Zadik
Stationary Points of Shallow Neural Networks with Quadratic Activation Function. CoRR (2019)
David Gamarnik, Aukosh Jagannath, Subhabrata Sen
The Overlap Gap Property in Principal Submatrix Recovery. CoRR (2019)
David Gamarnik, Ilias Zadik
The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property. CoRR (2019)
David Gamarnik, Julia Gaudio
Sparse High-Dimensional Isotonic Regression. NeurIPS (2019)
David Gamarnik, Eren C. Kizildag
High-Dimensional Linear Regression and Phase Retrieval via PSLQ Integer Relation Algorithm. ISIT (2019)
Uriel Feige, David Gamarnik, Joe Neeman, Miklós Z. Rácz, Prasad Tetali
Finding cliques using few probes. CoRR (2018)
David Gamarnik, Quan Li
On the max-cut of sparse random graphs. Random Struct. Algorithms 52 (2) (2018)
David Gamarnik
Computing the partition function of the Sherrington-Kirkpatrick model is hard on average. CoRR (2018)
Guy Bresler, David Gamarnik, Devavrat Shah
Learning Graphical Models From the Glauber Dynamics. IEEE Trans. Inf. Theory 64 (6) (2018)
David Gamarnik
Explicit construction of RIP matrices is Ramsey-hard. CoRR (2018)
Patrick Eschenfeldt, David Gamarnik
Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics. Math. Oper. Res. 43 (3) (2018)
Ilias Zadik, David Gamarnik
High Dimensional Linear Regression using Lattice Basis Reduction. NeurIPS (2018)
David Gamarnik, Quan Li, Hongyi Zhang
Matrix Completion from $O(n)$ Samples in Linear Time. COLT (2017)
David Gamarnik, Quan Li, Hongyi Zhang
Matrix Completion from O(n) Samples in Linear Time. CoRR (2017)
Ross Anderson, Itai Ashlagi, David Gamarnik, Yash Kanoria
Efficient Dynamic Barter Exchange. Oper. Res. 65 (6) (2017)
Christian Borgs, Jennifer T. Chayes, David Gamarnik
Convergent sequences of sparse graphs: A large deviations approach. Random Struct. Algorithms 51 (1) (2017)
David Gamarnik, Madhu Sudan
Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem. SIAM J. Comput. 46 (2) (2017)
David Gamarnik, Ilias Zadik
High Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transtition. COLT (2017)
Patrick Eschenfeldt, David Gamarnik
A Message Passing Algorithm for the Problem of Path Packing in Graphs. CoRR (2016)
David Gamarnik, John N. Tsitsiklis, Martin Zubeldia
Delay, Memory, and Messaging Tradeoffs in Distributed Service Systems. SIGMETRICS (2016)
David Gamarnik, Sidhant Misra
A Note on Alternating Minimization Algorithm for the Matrix Completion Problem. CoRR (2016)
Edward J. Anderson, David Gamarnik, Anton J. Kleywegt, Asuman E. Ozdaglar
Preface to the Special Issue on Information and Decisions in Social and Economic Networks. Oper. Res. 64 (3) (2016)
David Gamarnik, Sidhant Misra
A Note on Alternating Minimization Algorithm for the Matrix Completion Problem. IEEE Signal Process. Lett. 23 (10) (2016)
Ross Anderson, Itai Ashlagi, David Gamarnik, Michael Rees, Alvin E. Roth, Tayfun Sönmez, M. Utku Ünver
Kidney Exchange and the Alliance for Paired Donation: Operations Research Changes the Way Kidneys Are Transplanted. Interfaces 45 (1) (2015)
David Gamarnik, Dmitriy Katz, Sidhant Misra
Strong spatial mixing of list coloring of graphs. Random Struct. Algorithms 46 (4) (2015)
David Gamarnik, Dmitriy Katz
The stability of the deterministic Skorokhod problem is undecidable. Queueing Syst. Theory Appl. 79 (3-4) (2015)
Ross Anderson, Itai Ashlagi, David Gamarnik, Yash Kanoria
A dynamic model of barter exchange. SODA (2015)
David Gamarnik, Madhu Sudan
Limits of local algorithms over sparse random graphs. ITCS (2014)
Guy Bresler, David Gamarnik, Devavrat Shah
Learning graphical models from the Glauber dynamics. Allerton (2014)
Guy Bresler, David Gamarnik, Devavrat Shah
Hardness of parameter estimation in graphical models. NIPS (2014)
David Gamarnik, Madhu Sudan
Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem. CoRR (2014)
Guy Bresler, David Gamarnik, Devavrat Shah
Hardness of parameter estimation in graphical models. CoRR (2014)
Guy Bresler, David Gamarnik, Devavrat Shah
Learning graphical models from the Glauber dynamics. CoRR (2014)
David Gamarnik, Mathieu Hemery, Samuel Hetterich
Local Algorithms for Graphs. CoRR (2014)
Guy Bresler, David Gamarnik, Devavrat Shah
Structure learning of antiferromagnetic Ising models. CoRR (2014)
David Gamarnik, David A. Goldberg, Theophane Weber
Correlation Decay in Random Decision Networks. Math. Oper. Res. 39 (2) (2014)
Guy Bresler, David Gamarnik, Devavrat Shah
Structure learning of antiferromagnetic Ising models. NIPS (2014)
David Gamarnik, Madhu Sudan
Limits of local algorithms over sparse random graphs. Electron. Colloquium Comput. Complex. 20 (2013)
David Gamarnik, Madhu Sudan
Limits of local algorithms over sparse random graphs CoRR (2013)
David Gamarnik, Devavrat Shah, Yehua Wei
Belief Propagation for Min-Cost Network Flow: Convergence and Correctness. Oper. Res. 60 (2) (2012)
David Gamarnik, Dmitriy Katz, Sidhant Misra
Strong spatial mixing for list coloring of graphs CoRR (2012)
David Gamarnik, Alexander L. Stolyar
Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution. Queueing Syst. Theory Appl. 71 (1-2) (2012)
David Gamarnik, Dmitriy Katz
Correlation decay and deterministic FPTAS for counting colorings of a graph. J. Discrete Algorithms 12 (2012)
Abraham Flaxman, David Gamarnik, Gregory B. Sorkin
First-passage percolation on a ladder graph, and the path cost in a VCG auction. Random Struct. Algorithms 38 (3) (2011)
Venkat Chandrasekaran, Misha Chertkov, David Gamarnik, Devavrat Shah, Jinwoo Shin
Counting Independent Sets Using the Bethe Approximation. SIAM J. Discret. Math. 25 (2) (2011)
Dimitris Bertsimas, David Gamarnik, Alexander Anatoliy Rikun
Performance Analysis of Queueing Networks via Robust Optimization. Oper. Res. 59 (2) (2011)
David Gamarnik, Dmitriy Katz
A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix. J. Comput. Syst. Sci. 76 (8) (2010)
David Gamarnik, Devavrat Shah, Yehua Wei
Belief Propagation for Min-cost Network Flow: Convergence & Correctness. SODA (2010)
Mohsen Bayati, David Gamarnik, Prasad Tetali
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. STOC (2010)
David Gamarnik, Dmitriy Katz
Stability of Skorokhod problem is undecidable CoRR (2010)
David Gamarnik, David A. Goldberg
Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections. Comb. Probab. Comput. 19 (1) (2010)
David Gamarnik, Sean P. Meyn
On exponential ergodicity of multiclass queueing networks. Queueing Syst. Theory Appl. 65 (2) (2010)
David Gamarnik, David A. Goldberg, Theophane Weber
PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs. SODA (2010)
David Gamarnik, Dmitriy Katz
Sequential cavity method for computing limits of the log-partition function for lattice models. SODA (2009)
David Gamarnik, David A. Goldberg, Theophane Weber
Correlation Decay in Random Decision Networks CoRR (2009)
David Gamarnik, David A. Goldberg
Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections CoRR (2008)
Antar Bandyopadhyay, David Gamarnik
Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models. Random Struct. Algorithms 33 (4) (2008)
David Gamarnik, Dmitriy Katz
Correlation decay and deterministic FPTAS for counting list-colorings of a graph. SODA (2007)
Mohsen Bayati, David Gamarnik, Dimitriy A. Katz, Chandra Nair, Prasad Tetali
Simple deterministic approximation algorithms for counting matchings. STOC (2007)
David Gamarnik
On the Undecidability of Computing Stationary Distributions and Large Deviation Rates for Constrained Random Walks. Math. Oper. Res. 32 (2) (2007)
Abraham Flaxman, David Gamarnik, Gregory B. Sorkin
First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction. WINE (2006)
Nikhil Bansal, David Gamarnik
Handling load with less stress. Queueing Syst. Theory Appl. 54 (1) (2006)
David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz
Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method. Random Struct. Algorithms 28 (1) (2006)
Antar Bandyopadhyay, David Gamarnik
Counting without sampling: new algorithms for enumeration problems using statistical physics. SODA (2006)
Abraham D. Flaxman, David Gamarnik, Gregory B. Sorkin
Embracing the giant component. Random Struct. Algorithms 27 (3) (2005)
David Gamarnik
The expected value of random minimal length spanning tree of a complete graph. SODA (2005)
David Gamarnik, Maxim Sviridenko
Hamiltonian completions of sparse random graphs. Discret. Appl. Math. 152 (1-3) (2005)
David Gamarnik, Moshe Lewenstein, Maxim Sviridenko
An improved upper bound for the TSP in cubic 3-edge-connected graphs. Oper. Res. Lett. 33 (5) (2005)
Abraham Flaxman, David Gamarnik, Gregory B. Sorkin
Embracing the Giant Component. LATIN (2004)

David Gamarnik.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

David Gamarnik