David Gamarnik
Orcid: 0000-0001-8898-8778Affiliations:
- MIT Sloan School of Management
According to our database1,
David Gamarnik
authored at least 105 papers
between 1996 and 2024.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
Online presence:
On csauthors.net:
Bibliography
2024
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics.
SIAM J. Comput., February, 2024
2023
Random Struct. Algorithms, 2023
CoRR, 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
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
CoRR, 2021
Proceedings of the IEEE International Symposium on Information Theory, 2021
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
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
Math. Oper. Res., 2018
Computing the partition function of the Sherrington-Kirkpatrick model is hard on average.
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
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
Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, 2016
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
Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem.
CoRR, 2014
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 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
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
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
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
Oper. Res. Lett., 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
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
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