Publications (48)
Uniqueness of Gibbs Measures for Continuous Hardcore Models
David Gamarnik, Kavita Ramanan
Right-convergence of sparse random graphs
David Gamarnik
High Dimensional Linear Regression using Lattice Basis Reduction
David Gamarnik, Ilias Zadik
Belief Propagation for Min-cost Network Flow: Convergence and Correctness
David Gamarnik, Devavrat Shah, Yehua Wei
Limits of local algorithms over sparse random graphs
David Gamarnik, Madhu Sudan
A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix
David Gamarnik, Dmitriy Katz
Performance Analysis of Queueing Networks via Robust Optimization
Dimitris Bertsimas, David Gamarnik, Alexander Rikun
On the Max-Cut of Sparse Random Graphs
David Gamarnik, Quan Li
Random MAX SAT, Random MAX CUT, and Their Phase Transitions
Don Coppersmith, David Gamarnik, Mohammad Hajiaghayi +1
Structure learning of antiferromagnetic Ising models
Guy Bresler, David Gamarnik, Devavrat Shah
Hardness of parameter estimation in graphical models
Guy Bresler, David Gamarnik, Devavrat Shah
Sequential cavity method for computing free energy and surface pressure
David Gamarnik, Dmitriy Katz
Finding cliques using few probes
Uriel Feige, David Gamarnik, Joe Neeman +2
Explicit construction of RIP matrices is Ramsey-hard
David Gamarnik
Counting without sampling. New algorithms for enumeration problems using statistical physics
Antar Bandyopadhyay, David Gamarnik
Matrix Completion from $O(n)$ Samples in Linear Time
David Gamarnik, Quan Li, Hongyi Zhang
Instability in Stochastic and Fluid Queueing Networks
David Gamarnik, John Hasenbein
Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime. Asymptotics of the stationary distribution
David Gamarnik, Alexander Stolyar
Strong spatial mixing for list coloring of graphs
David Gamarnik, Dmitry Katz, Sidhant Misra
Steady-state $\mathit{GI}/\mathit{GI}/\mathit{n}$ queue in the Halfin-Whitt regime
David Gamarnik, David A. Goldberg
Dynamics of exponential linear map in functional space
David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz
Join the Shortest Queue with Many Servers. The Heavy Traffic Asymptotics
Patrick Eschenfeldt, David Gamarnik
Local Algorithms for Graphs
David Gamarnik, Mathieu Hemery, Samuel Hetterich
Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections
David Gamarnik, David Goldberg
Linear Phase Transition in Random Linear Constraint Satisfaction Problem
David Gamarnik
On the rate of convergence to stationarity of the M/M/N queue in the Halfin-Whitt regime
David Gamarnik, David A. Goldberg
A lower bound on the queueing delay in resource constrained load balancing
David Gamarnik, John N. Tsitsiklis, Martin Zubeldia
A Message Passing Algorithm for the Problem of Path Packing in Graphs
Patrick Eschenfeldt, David Gamarnik
Finding a Large Submatrix of a Gaussian Random Matrix
David Gamarnik, Quan Li
Stability of Skorokhod problem is undecidable
David Gamarnik, Dmitriy Katz
The diameter of a long range percolation graph
Don Coppersmith, David Gamarnik, Maxim Sviridenko
On Exponential Ergodicity of Multiclass Queueing Networks
David Gamarnik, Sean Meyn
Correlation decay and deterministic FPTAS for counting list-colorings of a graph
David Gamarnik, Dmitriy Katz
Giant Component in Random Multipartite Graphs with Given Degree Sequences
David Gamarnik, Sidhant Misra
Computing stationary probability distributions and large deviation rates for constrained random walks. The undecidability results
David Gamarnik
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
Mohsen Bayati, David Gamarnik, Prasad Tetali
A Transposition Rule Analysis Based on a Particle Process
David Gamarnik, Petar Momcilovic
Supermarket Queueing System in the Heavy Traffic Regime. Short Queue Dynamics
Patrick Eschenfeldt, David Gamarnik
On deciding stability of multiclass queueing networks under buffer priority scheduling policies
David Gamarnik, Dmitriy Katz
Steady-state analysis of a multi-server queue in the Halfin-Whitt regime
David Gamarnik, Petar Momcilovic
Delay, memory, and messaging tradeoffs in distributed service systems
David Gamarnik, John N. Tsitsiklis, Martin Zubeldia
Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem
David Gamarnik, Madhu Sudan
Sparse High-Dimensional Isotonic Regression
David Gamarnik, Julia Gaudio
Correlation Decay in Random Decision Networks
David Gamarnik, David Goldberg, Theophane Weber
Convergent sequences of sparse graphs: A large deviations approach
Christian Borgs, Jennifer Chayes, David Gamarnik
Validity of heavy traffic steady-state approximations in generalized Jackson Networks
David Gamarnik, Assaf Zeevi
Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method
David Gamarnik, Tomasz Nowicki, Grzegorz Swirscsz
Learning graphical models from the Glauber dynamics
Guy Bresler, David Gamarnik, Devavrat Shah