David Gamarnik

143 papers A* 27A 1B 5Journal 103Unranked 7

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Rigorous Asymptotics for First-Order Algorithms Through the Dynamical Cavity Method. CoRR Yatin Dandi, David Gamarnik, Francisco Pernice, Lenka Zdeborová
2025	J	`jnl`	Decoded Quantum Interferometry Requires Structure. CoRR Eric R. Anschuetz, David Gamarnik, Jonathan Z. Lu
2025	J	`jnl`	Densest Subgraphs of a Dense Erdös-Rényi Graph. Asymptotics, Landscape, and Universality. SIAM J. Discret. Math. Houssam El Cheairi, David Gamarnik
2025	J	`jnl`	Hardness of Sampling Solutions From the Symmetric Binary Perceptron. Random Struct. Algorithms Ahmed El Alaoui, David Gamarnik
2025	J	`jnl`	Optimal Hardness of Online Algorithms for Large Independent Sets. CoRR David Gamarnik, Eren C. Kizildag, Lutz Warnke
2025	J	`jnl`	Stationary Points of a Shallow Neural Network with Quadratic Activations and the Global Optimality of the Gradient Descent Algorithm. Math. Oper. Res. David Gamarnik, Eren C. Kizildag, Ilias Zadik
2025	J	`jnl`	The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements. CoRR Youssef Chaabouni, David Gamarnik
2025	J	`jnl`	Theoretical Compression Bounds for Wide Multilayer Perceptrons. CoRR Houssam El Cheairi, David Gamarnik, Rahul Mazumder
2025	J	`jnl`	Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes. CoRR David Gamarnik
2024	J	`jnl`	Algorithmic Universality, Low-Degree Polynomials, and Max-Cut in Sparse Random Graphs. CoRR Houssam El Cheairi, David Gamarnik
2024	J	`jnl`	Cliques, Chromatic Number, and Independent Sets in the Semi-random Process. SIAM J. Discret. Math. David Gamarnik, Mihyun Kang, Pawel Pralat
2024	J	`jnl`	Combinatorial NLTS From the Overlap Gap Property. Quantum Eric R. Anschuetz, David Gamarnik, Bobak T. Kiani
2024	J	`jnl`	Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics. SIAM J. Comput. David Gamarnik, Aukosh Jagannath, Alexander S. Wein
2024	J	`jnl`	Hardness of sampling solutions from the Symmetric Binary Perceptron. CoRR Ahmed El Alaoui, David Gamarnik
2024	J	`jnl`	Integrating High-Dimensional Functions Deterministically. CoRR David Gamarnik, Devin Smedira
2023	J	`jnl`	Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~\cite{schuetz2022combinatorial}, \cite{angelini2023modern}, \cite{schuetz2023reply}. CoRR David Gamarnik
2023	J	`jnl`	Cliques, Chromatic Number, and Independent Sets in the Semi-random Process. CoRR David Gamarnik, Mihyun Kang, Pawel Pralat
2023	J	`jnl`	Computing the Volume of a Restricted Independent Set Polytope Deterministically. CoRR David Gamarnik, Devin Smedira
2023	J	`jnl`	Correlation decay and the absence of zeros property of partition functions. Random Struct. Algorithms David Gamarnik
2023	A*	`conf`	Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization. COLT David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu
2023	J	`jnl`	Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization. CoRR David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu
2023	J	`jnl`	Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique. CoRR David Gamarnik, Elchanan Mossel, Ilias Zadik
2022	A*	`conf`	Algorithms and Barriers in the Symmetric Binary Perceptron Model. FOCS David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu
2022	J	`jnl`	Algorithms and Barriers in the Symmetric Binary Perceptron Model. CoRR David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu
2022	J	`jnl`	Disordered Systems Insights on Computational Hardness. CoRR David Gamarnik, Cristopher Moore, Lenka Zdeborová
2022	A*	`conf`	Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. FOCS Joao Basso, David Gamarnik, Song Mei, Leo Zhou
2022	J	`jnl`	Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. CoRR Joao Basso, David Gamarnik, Song Mei, Leo Zhou
2022	J	`jnl`	Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks. IEEE Trans. Signal Process. David Gamarnik, Eren C. Kizildag, Ilias Zadik
2022	J	`jnl`	Stability, Memory, and Messaging Trade-Offs in Heterogeneous Service Systems. Math. Oper. Res. David Gamarnik, John N. Tsitsiklis, Martin Zubeldia
2022	B	`conf`	The Random Number Partitioning Problem: Overlap Gap Property and Algorithmic Barriers. ISIT David Gamarnik, Eren C. Kizildag
2021	J	`jnl`	Circuit Lower Bounds for the p-Spin Optimization Problem. CoRR David Gamarnik, Aukosh Jagannath, Alexander S. Wein
2021	J	`jnl`	Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection. IEEE Trans. Inf. Theory David Gamarnik, Eren C. Kizildag, Ilias Zadik
2021	J	`jnl`	Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks. CoRR David Gamarnik, Eren C. Kizildag, Ilias Zadik
2021	B	`conf`	Self-Regularity of Output Weights for Overparameterized Two-Layer Neural Networks. ISIT David Gamarnik, Eren C. Kizildag, Ilias Zadik
2021	J	`jnl`	The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures. CoRR David Gamarnik
2020	B	`conf`	Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average. ISIT David Gamarnik, Eren C. Kizildag
2020	J	`jnl`	Correlation Decay and the Absence of Zeros Property of Partition Functions. CoRR David Gamarnik
2020	J	`jnl`	Finding cliques using few probes. Random Struct. Algorithms Uriel Feige, David Gamarnik, Joe Neeman, Miklós Z. Rácz, Prasad Tetali
2020	A*	`conf`	Low-Degree Hardness of Random Optimization Problems. FOCS David Gamarnik, Aukosh Jagannath, Alexander S. Wein
2020	J	`jnl`	Low-Degree Hardness of Random Optimization Problems. CoRR David Gamarnik, Aukosh Jagannath, Alexander S. Wein
2020	J	`jnl`	Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena. CoRR Matt Emschwiller, David Gamarnik, Eren C. Kizildag, Ilias Zadik
2020	J	`jnl`	Stability, memory, and messaging tradeoffs in heterogeneous service systems. CoRR David Gamarnik, John N. Tsitsiklis, Martin Zubeldia
2020	J	`jnl`	The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case. CoRR Edward Farhi, David Gamarnik, Sam Gutmann
2019	B	`conf`	High-Dimensional Linear Regression and Phase Retrieval via PSLQ Integer Relation Algorithm. ISIT David Gamarnik, Eren C. Kizildag
2019	A*	`conf`	Sparse High-Dimensional Isotonic Regression. NeurIPS David Gamarnik, Julia Gaudio
2019	J	`jnl`	Stationary Points of Shallow Neural Networks with Quadratic Activation Function. CoRR David Gamarnik, Eren C. Kizildag, Ilias Zadik
2019	J	`jnl`	The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property. CoRR David Gamarnik, Ilias Zadik
2019	J	`jnl`	The Overlap Gap Property in Principal Submatrix Recovery. CoRR David Gamarnik, Aukosh Jagannath, Subhabrata Sen
2018	J	`jnl`	Computing the partition function of the Sherrington-Kirkpatrick model is hard on average. CoRR David Gamarnik
2018	J	`jnl`	Explicit construction of RIP matrices is Ramsey-hard. CoRR David Gamarnik
2018	J	`jnl`	Finding cliques using few probes. CoRR Uriel Feige, David Gamarnik, Joe Neeman, Miklós Z. Rácz, Prasad Tetali
2018	A*	`conf`	High Dimensional Linear Regression using Lattice Basis Reduction. NeurIPS Ilias Zadik, David Gamarnik
2018	J	`jnl`	Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics. Math. Oper. Res. Patrick Eschenfeldt, David Gamarnik
2018	J	`jnl`	Learning Graphical Models From the Glauber Dynamics. IEEE Trans. Inf. Theory Guy Bresler, David Gamarnik, Devavrat Shah
2018	J	`jnl`	On the max-cut of sparse random graphs. Random Struct. Algorithms David Gamarnik, Quan Li
2017	J	`jnl`	Convergent sequences of sparse graphs: A large deviations approach. Random Struct. Algorithms Christian Borgs, Jennifer T. Chayes, David Gamarnik
2017	J	`jnl`	Efficient Dynamic Barter Exchange. Oper. Res. Ross Anderson, Itai Ashlagi, David Gamarnik, Yash Kanoria
2017	A*	`conf`	High Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transtition. COLT David Gamarnik, Ilias Zadik
2017	A*	`conf`	Matrix Completion from $O(n)$ Samples in Linear Time. COLT David Gamarnik, Quan Li, Hongyi Zhang
2017	J	`jnl`	Matrix Completion from O(n) Samples in Linear Time. CoRR David Gamarnik, Quan Li, Hongyi Zhang
2017	J	`jnl`	Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem. SIAM J. Comput. David Gamarnik, Madhu Sudan
2016	J	`jnl`	A Message Passing Algorithm for the Problem of Path Packing in Graphs. CoRR Patrick Eschenfeldt, David Gamarnik
2016	J	`jnl`	A Note on Alternating Minimization Algorithm for the Matrix Completion Problem. CoRR David Gamarnik, Sidhant Misra
2016	J	`jnl`	A Note on Alternating Minimization Algorithm for the Matrix Completion Problem. IEEE Signal Process. Lett. David Gamarnik, Sidhant Misra
2016	A*	`conf`	Delay, Memory, and Messaging Tradeoffs in Distributed Service Systems. SIGMETRICS David Gamarnik, John N. Tsitsiklis, Martin Zubeldia
2016	J	`jnl`	Preface to the Special Issue on Information and Decisions in Social and Economic Networks. Oper. Res. Edward J. Anderson, David Gamarnik, Anton J. Kleywegt, Asuman E. Ozdaglar
2015	A*	`conf`	A dynamic model of barter exchange. SODA Ross Anderson, Itai Ashlagi, David Gamarnik, Yash Kanoria
2015	J	`jnl`	Kidney Exchange and the Alliance for Paired Donation: Operations Research Changes the Way Kidneys Are Transplanted. Interfaces Ross Anderson, Itai Ashlagi, David Gamarnik, Michael Rees, Alvin E. Roth, Tayfun Sönmez, M. Utku Ünver
2015	J	`jnl`	Strong spatial mixing of list coloring of graphs. Random Struct. Algorithms David Gamarnik, Dmitriy Katz, Sidhant Misra
2015	J	`jnl`	The stability of the deterministic Skorokhod problem is undecidable. Queueing Syst. Theory Appl. David Gamarnik, Dmitriy Katz
2014	J	`jnl`	Correlation Decay in Random Decision Networks. Math. Oper. Res. David Gamarnik, David A. Goldberg, Theophane Weber
2014	—	`conf`	Hardness of parameter estimation in graphical models. NIPS Guy Bresler, David Gamarnik, Devavrat Shah
2014	J	`jnl`	Hardness of parameter estimation in graphical models. CoRR Guy Bresler, David Gamarnik, Devavrat Shah
2014	—	`conf`	Learning graphical models from the Glauber dynamics. Allerton Guy Bresler, David Gamarnik, Devavrat Shah
2014	J	`jnl`	Learning graphical models from the Glauber dynamics. CoRR Guy Bresler, David Gamarnik, Devavrat Shah
2014	A	`conf`	Limits of local algorithms over sparse random graphs. ITCS David Gamarnik, Madhu Sudan
2014	J	`jnl`	Local Algorithms for Graphs. CoRR David Gamarnik, Mathieu Hemery, Samuel Hetterich
2014	J	`jnl`	Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem. CoRR David Gamarnik, Madhu Sudan
2014	—	`conf`	Structure learning of antiferromagnetic Ising models. NIPS Guy Bresler, David Gamarnik, Devavrat Shah
2014	J	`jnl`	Structure learning of antiferromagnetic Ising models. CoRR Guy Bresler, David Gamarnik, Devavrat Shah
2013	J	`jnl`	Limits of local algorithms over sparse random graphs CoRR David Gamarnik, Madhu Sudan
2013	J	`jnl`	Limits of local algorithms over sparse random graphs. Electron. Colloquium Comput. Complex. David Gamarnik, Madhu Sudan
2012	J	`jnl`	Belief Propagation for Min-Cost Network Flow: Convergence and Correctness. Oper. Res. David Gamarnik, Devavrat Shah, Yehua Wei
2012	J	`jnl`	Correlation decay and deterministic FPTAS for counting colorings of a graph. J. Discrete Algorithms David Gamarnik, Dmitriy Katz
2012	J	`jnl`	Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution. Queueing Syst. Theory Appl. David Gamarnik, Alexander L. Stolyar
2012	J	`jnl`	Strong spatial mixing for list coloring of graphs CoRR David Gamarnik, Dmitriy Katz, Sidhant Misra
2011	J	`jnl`	Counting Independent Sets Using the Bethe Approximation. SIAM J. Discret. Math. Venkat Chandrasekaran, Misha Chertkov, David Gamarnik, Devavrat Shah, Jinwoo Shin
2011	J	`jnl`	First-passage percolation on a ladder graph, and the path cost in a VCG auction. Random Struct. Algorithms Abraham Flaxman, David Gamarnik, Gregory B. Sorkin
2011	J	`jnl`	Performance Analysis of Queueing Networks via Robust Optimization. Oper. Res. Dimitris Bertsimas, David Gamarnik, Alexander Anatoliy Rikun
2010	J	`jnl`	A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix. J. Comput. Syst. Sci. David Gamarnik, Dmitriy Katz
2010	A*	`conf`	Belief Propagation for Min-cost Network Flow: Convergence & Correctness. SODA David Gamarnik, Devavrat Shah, Yehua Wei
2010	A*	`conf`	Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. STOC Mohsen Bayati, David Gamarnik, Prasad Tetali
2010	J	`jnl`	On exponential ergodicity of multiclass queueing networks. Queueing Syst. Theory Appl. David Gamarnik, Sean P. Meyn
2010	A*	`conf`	PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs. SODA David Gamarnik, David A. Goldberg, Theophane Weber
2010	J	`jnl`	Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections. Comb. Probab. Comput. David Gamarnik, David A. Goldberg
2010	J	`jnl`	Stability of Skorokhod problem is undecidable CoRR David Gamarnik, Dmitriy Katz
2009	J	`jnl`	Correlation Decay in Random Decision Networks CoRR David Gamarnik, David A. Goldberg, Theophane Weber
2009	A*	`conf`	Sequential cavity method for computing limits of the log-partition function for lattice models. SODA David Gamarnik, Dmitriy Katz
2008	J	`jnl`	Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models. Random Struct. Algorithms Antar Bandyopadhyay, David Gamarnik
2008	J	`jnl`	Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections CoRR David Gamarnik, David A. Goldberg
2007	A*	`conf`	Correlation decay and deterministic FPTAS for counting list-colorings of a graph. SODA David Gamarnik, Dmitriy Katz
2007	J	`jnl`	On the Undecidability of Computing Stationary Distributions and Large Deviation Rates for Constrained Random Walks. Math. Oper. Res. David Gamarnik
2007	A*	`conf`	Simple deterministic approximation algorithms for counting matchings. STOC Mohsen Bayati, David Gamarnik, Dimitriy A. Katz, Chandra Nair, Prasad Tetali
2006	A*	`conf`	Counting without sampling: new algorithms for enumeration problems using statistical physics. SODA Antar Bandyopadhyay, David Gamarnik
2006	—	`conf`	First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction. WINE Abraham Flaxman, David Gamarnik, Gregory B. Sorkin
2006	J	`jnl`	Handling load with less stress. Queueing Syst. Theory Appl. Nikhil Bansal, David Gamarnik
2006	J	`jnl`	Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method. Random Struct. Algorithms David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz
2005	J	`jnl`	An improved upper bound for the TSP in cubic 3-edge-connected graphs. Oper. Res. Lett. David Gamarnik, Moshe Lewenstein, Maxim Sviridenko
2005	J	`jnl`	Embracing the giant component. Random Struct. Algorithms Abraham D. Flaxman, David Gamarnik, Gregory B. Sorkin
2005	J	`jnl`	Hamiltonian completions of sparse random graphs. Discret. Appl. Math. David Gamarnik, Maxim Sviridenko
2005	A*	`conf`	The expected value of random minimal length spanning tree of a complete graph. SODA David Gamarnik
2004	J	`jnl`	An asymptotic optimality of the transposition rule for linear lists. SIGMETRICS Perform. Evaluation Rev. David Gamarnik, Petar Momcilovic
2004	B	`conf`	Embracing the Giant Component. LATIN Abraham Flaxman, David Gamarnik, Gregory B. Sorkin
2004	A*	`conf`	Linear phase transition in random linear constraint satisfaction problems. SODA David Gamarnik
2004	—	`conf`	Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results Using the Local Weak Convergence Method. APPROX-RANDOM David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz
2004	J	`jnl`	On the Value of a Random Minimum Weight Steiner Tree. Comb. Béla Bollobás, David Gamarnik, Oliver Riordan, Benny Sudakov
2004	J	`jnl`	Random MAX SAT, random MAX CUT, and their phase transitions. Random Struct. Algorithms Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin
2004	J	`jnl`	Stochastic Bandwidth Packing Process: Stability Conditions via Lyapunov Function Technique. Queueing Syst. Theory Appl. David Gamarnik
2003	J	`jnl`	Extension of the PAC framework to finite and countable Markov chains. IEEE Trans. Inf. Theory David Gamarnik
2003	J	`jnl`	From Fluid Relaxations to Practical Algorithms for High-Multiplicity Job-Shop Scheduling: The Holding Cost Objective. Oper. Res. Dimitris Bertsimas, David Gamarnik, Jay Sethuraman
2003	—	`conf`	Linear Phase Transition in Random Linear Constraint Satisfaction Problems. DRW David Gamarnik
2003	A*	`conf`	Random MAX SAT, random MAX CUT, and their phase transitions. SODA Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin
2003	J	`jnl`	Stability of Adaptive and Nonadaptive Packet Routing Policies in Adversarial Queueing Networks. SIAM J. Comput. David Gamarnik
2003	J	`jnl`	Weak instability in stochastic and fluid queueing networks. SIGMETRICS Perform. Evaluation Rev. David Gamarnik, John J. Hasenbein
2002	J	`jnl`	Computing stationary probability distributions and large deviation rates for constrained random walks.: the undecidability results. SIGMETRICS Perform. Evaluation Rev. David Gamarnik
2002	J	`jnl`	On Deciding Stability of Constrained Homogeneous Random Walks and Queueing Systems. Math. Oper. Res. David Gamarnik
2002	A*	`conf`	The diameter of a long range percolation graph. SODA Don Coppersmith, David Gamarnik, Maxim Sviridenko
2002	J	`jnl`	The diameter of a long-range percolation graph. Random Struct. Algorithms Don Coppersmith, David Gamarnik, Maxim Sviridenko
2001	J	`jnl`	On deciding stability of constrained random walks and queueing systems. SIGMETRICS Perform. Evaluation Rev. David Gamarnik
2001	J	`jnl`	Stochastic online binpacking problem: exact conditions for bounded expected queue lengths under the best fit packing heuristic. SIGMETRICS Perform. Evaluation Rev. David Gamarnik
2000	A*	`conf`	On deciding stability of scheduling policies in queueing systems. SODA David Gamarnik
2000	—	`conf`	Performance of multiclass Markovian queueing networks. CDC Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis
2000	J	`jnl`	Using fluid models to prove stability of adversarial queueing networks. IEEE Trans. Autom. Control. David Gamarnik
1999	J	`jnl`	Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet Routing. J. Algorithms Dimitris Bertsimas, David Gamarnik
1999	J	`jnl`	Estimation of Time-Varying Parameters in Statistical Models: An Optimization Approach. Mach. Learn. Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis
1999	A*	`conf`	Extension of the PAC Framework to Finite and Countable Markov Chains. COLT David Gamarnik
1999	J	`jnl`	Performance analysis of multiclass queueing networks. SIGMETRICS Perform. Evaluation Rev. Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis
1999	A*	`conf`	Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks. STOC David Gamarnik
1998	A*	`conf`	Efficient Learning of Monotone Concepts via Quadratic Optimization. COLT David Gamarnik
1998	A*	`conf`	Stability of Adversarial Queues via Fluid Models. FOCS David Gamarnik
1997	J	`jnl`	Correction to "Stability Conditions for Multiclass Fluid Queueing Networks". IEEE Trans. Autom. Control. Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis
1997	A*	`conf`	Estimation of Time-Varying Parameters in Statistical Models: An Optimization Approach. COLT Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis
1996	J	`jnl`	Stability conditions for multiclass fluid queueing networks. IEEE Trans. Autom. Control. Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis