David Gamarnik

Affiliations:
  • MIT Sloan School of Management


According to our database1, David Gamarnik authored at least 102 papers between 1996 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Correlation decay and the absence of zeros property of partition functions.
Random Struct. Algorithms, 2023

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique.
CoRR, 2023

Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~\cite{schuetz2022combinatorial}, \cite{angelini2023modern}, \cite{schuetz2023reply}.
CoRR, 2023

Cliques, Chromatic Number, and Independent Sets in the Semi-random Process.
CoRR, 2023

Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization.
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022
Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks.
IEEE Trans. Signal Process., 2022

Stability, Memory, and Messaging Trade-Offs in Heterogeneous Service Systems.
Math. Oper. Res., 2022

Disordered Systems Insights on Computational Hardness.
CoRR, 2022

The Random Number Partitioning Problem: Overlap Gap Property and Algorithmic Barriers.
Proceedings of the IEEE International Symposium on Information Theory, 2022

Algorithms and Barriers in the Symmetric Binary Perceptron Model.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021
Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection.
IEEE Trans. Inf. Theory, 2021

The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures.
CoRR, 2021

Circuit Lower Bounds for the p-Spin Optimization Problem.
CoRR, 2021

Self-Regularity of Output Weights for Overparameterized Two-Layer Neural Networks.
Proceedings of the IEEE International Symposium on Information Theory, 2021

2020
Finding cliques using few probes.
Random Struct. Algorithms, 2020

Stability, memory, and messaging tradeoffs in heterogeneous service systems.
CoRR, 2020

The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case.
CoRR, 2020

Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena.
CoRR, 2020

Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average.
Proceedings of the IEEE International Symposium on Information Theory, 2020

Low-Degree Hardness of Random Optimization Problems.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019
Stationary Points of Shallow Neural Networks with Quadratic Activation Function.
CoRR, 2019

The Overlap Gap Property in Principal Submatrix Recovery.
CoRR, 2019

The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property.
CoRR, 2019

Sparse High-Dimensional Isotonic Regression.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

High-Dimensional Linear Regression and Phase Retrieval via PSLQ Integer Relation Algorithm.
Proceedings of the IEEE International Symposium on Information Theory, 2019

2018
Learning Graphical Models From the Glauber Dynamics.
IEEE Trans. Inf. Theory, 2018

On the max-cut of sparse random graphs.
Random Struct. Algorithms, 2018

Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics.
Math. Oper. Res., 2018

Computing the partition function of the Sherrington-Kirkpatrick model is hard on average.
CoRR, 2018

Explicit construction of RIP matrices is Ramsey-hard.
CoRR, 2018

High Dimensional Linear Regression using Lattice Basis Reduction.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017
Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem.
SIAM J. Comput., 2017

Convergent sequences of sparse graphs: A large deviations approach.
Random Struct. Algorithms, 2017

Efficient Dynamic Barter Exchange.
Oper. Res., 2017

Matrix Completion from $O(n)$ Samples in Linear Time.
Proceedings of the 30th Conference on Learning Theory, 2017

High Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transtition.
Proceedings of the 30th Conference on Learning Theory, 2017

2016
A Note on Alternating Minimization Algorithm for the Matrix Completion Problem.
IEEE Signal Process. Lett., 2016

Preface to the Special Issue on Information and Decisions in Social and Economic Networks.
Oper. Res., 2016

A Message Passing Algorithm for the Problem of Path Packing in Graphs.
CoRR, 2016

Delay, Memory, and Messaging Tradeoffs in Distributed Service Systems.
Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, 2016

2015
Strong spatial mixing of list coloring of graphs.
Random Struct. Algorithms, 2015

The stability of the deterministic Skorokhod problem is undecidable.
Queueing Syst. Theory Appl., 2015

Kidney Exchange and the Alliance for Paired Donation: Operations Research Changes the Way Kidneys Are Transplanted.
Interfaces, 2015

A dynamic model of barter exchange.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014
Correlation Decay in Random Decision Networks.
Math. Oper. Res., 2014

Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem.
CoRR, 2014

Local Algorithms for Graphs.
CoRR, 2014

Structure learning of antiferromagnetic Ising models.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Hardness of parameter estimation in graphical models.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

2013
Limits of local algorithms over sparse random graphs.
Electron. Colloquium Comput. Complex., 2013

2012
Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution.
Queueing Syst. Theory Appl., 2012

Correlation decay and deterministic FPTAS for counting colorings of a graph.
J. Discrete Algorithms, 2012

Belief Propagation for Min-Cost Network Flow: Convergence and Correctness.
Oper. Res., 2012

2011
Counting Independent Sets Using the Bethe Approximation.
SIAM J. Discret. Math., 2011

First-passage percolation on a ladder graph, and the path cost in a VCG auction.
Random Struct. Algorithms, 2011

Performance Analysis of Queueing Networks via Robust Optimization.
Oper. Res., 2011

2010
On exponential ergodicity of multiclass queueing networks.
Queueing Syst. Theory Appl., 2010

A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix.
J. Comput. Syst. Sci., 2010

Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections.
Comb. Probab. Comput., 2010

Stability of Skorokhod problem is undecidable
CoRR, 2010

Combinatorial approach to the interpolation method and scaling limits in sparse random graphs.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Belief Propagation for Min-cost Network Flow: Convergence & Correctness.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009
Sequential cavity method for computing limits of the log-partition function for lattice models.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008
Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models.
Random Struct. Algorithms, 2008

2007
On the Undecidability of Computing Stationary Distributions and Large Deviation Rates for Constrained Random Walks.
Math. Oper. Res., 2007

Simple deterministic approximation algorithms for counting matchings.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Correlation decay and deterministic FPTAS for counting list-colorings of a graph.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method.
Random Struct. Algorithms, 2006

Handling load with less stress.
Queueing Syst. Theory Appl., 2006

First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Counting without sampling: new algorithms for enumeration problems using statistical physics.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005
Embracing the giant component.
Random Struct. Algorithms, 2005

An improved upper bound for the TSP in cubic 3-edge-connected graphs.
Oper. Res. Lett., 2005

Hamiltonian completions of sparse random graphs.
Discret. Appl. Math., 2005

The expected value of random minimal length spanning tree of a complete graph.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004
An asymptotic optimality of the transposition rule for linear lists.
SIGMETRICS Perform. Evaluation Rev., 2004

Random MAX SAT, random MAX CUT, and their phase transitions.
Random Struct. Algorithms, 2004

Stochastic Bandwidth Packing Process: Stability Conditions via Lyapunov Function Technique.
Queueing Syst. Theory Appl., 2004

On the Value of a Random Minimum Weight Steiner Tree.
Comb., 2004

Linear phase transition in random linear constraint satisfaction problems.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003
Extension of the PAC framework to finite and countable Markov chains.
IEEE Trans. Inf. Theory, 2003

Weak instability in stochastic and fluid queueing networks.
SIGMETRICS Perform. Evaluation Rev., 2003

Stability of Adaptive and Nonadaptive Packet Routing Policies in Adversarial Queueing Networks.
SIAM J. Comput., 2003

From Fluid Relaxations to Practical Algorithms for High-Multiplicity Job-Shop Scheduling: The Holding Cost Objective.
Oper. Res., 2003

2002
Computing stationary probability distributions and large deviation rates for constrained random walks.: the undecidability results.
SIGMETRICS Perform. Evaluation Rev., 2002

The diameter of a long-range percolation graph.
Random Struct. Algorithms, 2002

On Deciding Stability of Constrained Homogeneous Random Walks and Queueing Systems.
Math. Oper. Res., 2002

2001
On deciding stability of constrained random walks and queueing systems.
SIGMETRICS Perform. Evaluation Rev., 2001

Stochastic online binpacking problem: exact conditions for bounded expected queue lengths under the best fit packing heuristic.
SIGMETRICS Perform. Evaluation Rev., 2001

2000
Using fluid models to prove stability of adversarial queueing networks.
IEEE Trans. Autom. Control., 2000

On deciding stability of scheduling policies in queueing systems.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Performance of multiclass Markovian queueing networks.
Proceedings of the 39th IEEE Conference on Decision and Control, 2000

1999
Performance analysis of multiclass queueing networks.
SIGMETRICS Perform. Evaluation Rev., 1999

Estimation of Time-Varying Parameters in Statistical Models: An Optimization Approach.
Mach. Learn., 1999

Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet Routing.
J. Algorithms, 1999

Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998
Stability of Adversarial Queues via Fluid Models.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Efficient Learning of Monotone Concepts via Quadratic Optimization.
Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998

1997
Correction to "Stability Conditions for Multiclass Fluid Queueing Networks".
IEEE Trans. Autom. Control., 1997

1996
Stability conditions for multiclass fluid queueing networks.
IEEE Trans. Autom. Control., 1996


  Loading...