# David Gamarnik

Affiliations:- MIT Sloan School of Management

According to our database

Collaborative distances:

^{1}, David Gamarnik authored at least 102 papers between 1996 and 2023.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Dataset Other## Links

#### Online presence:

#### On csauthors.net:

## Bibliography

2023

Random Struct. Algorithms, 2023

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

CoRR, 2023

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

Math. Oper. Res., 2022

CoRR, 2022

The Random Number Partitioning Problem: Overlap Gap Property and Algorithmic Barriers.

Proceedings of the IEEE International Symposium on Information Theory, 2022

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

CoRR, 2021

Self-Regularity of Output Weights for Overparameterized Two-Layer Neural Networks.

Proceedings of the IEEE International Symposium on Information Theory, 2021

2020

Random Struct. Algorithms, 2020

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

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

CoRR, 2019

CoRR, 2019

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

CoRR, 2019

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

IEEE Trans. Inf. Theory, 2018

Random Struct. Algorithms, 2018

Math. Oper. Res., 2018

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

CoRR, 2018

CoRR, 2018

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017

SIAM J. Comput., 2017

Random Struct. Algorithms, 2017

Oper. Res., 2017

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

IEEE Signal Process. Lett., 2016

Preface to the Special Issue on Information and Decisions in Social and Economic Networks.

Oper. Res., 2016

CoRR, 2016

Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, 2016

2015

Random Struct. Algorithms, 2015

Queueing Syst. Theory Appl., 2015

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

Interfaces, 2015

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Math. Oper. Res., 2014

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

CoRR, 2014

CoRR, 2014

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

2013

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

J. Discrete Algorithms, 2012

Oper. Res., 2012

2011

SIAM J. Discret. Math., 2011

Random Struct. Algorithms, 2011

Oper. Res., 2011

2010

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

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

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

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

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

Queueing Syst. Theory Appl., 2006

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

Random Struct. Algorithms, 2005

Oper. Res. Lett., 2005

Discret. Appl. Math., 2005

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

SIGMETRICS Perform. Evaluation Rev., 2004

Random Struct. Algorithms, 2004

Stochastic Bandwidth Packing Process: Stability Conditions via Lyapunov Function Technique.

Queueing Syst. Theory Appl., 2004

Comb., 2004

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003

IEEE Trans. Inf. Theory, 2003

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

Random Struct. Algorithms, 2002

On Deciding Stability of Constrained Homogeneous Random Walks and Queueing Systems.

Math. Oper. Res., 2002

2001

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

IEEE Trans. Autom. Control., 2000

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Proceedings of the 39th IEEE Conference on Decision and Control, 2000

1999

SIGMETRICS Perform. Evaluation Rev., 1999

Estimation of Time-Varying Parameters in Statistical Models: An Optimization Approach.

Mach. Learn., 1999

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

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998

1997

IEEE Trans. Autom. Control., 1997

1996

IEEE Trans. Autom. Control., 1996