David Gamarnik

David Gamarnik is the _Nanyang Technological University Professor _and Professor of Operations Research at the MIT Sloan School of Management.

His research interests include applied probability and stochastic processes with application to queuing theory, theory of random combinatorial structures and algorithms, scheduling, and various business processes, including call centers, manufacturing, and communications networks.

Gamarnik has served as a research staff member at the Department of Mathematical Sciences, IBM Research, where he worked on various projects with industrial applications, including disaster recovery, performance in business processes, call centers, and operational resilience. Gamarnik is a member of the Institute of Mathematical Statistics, Bernoulli Society, INFORMS, and the American Mathematical Society, and serves on the editorial board of both Operations Research and the Annals of Applied Probability. He is the recipient of the 2004 Erlang Prize from the INFORMS Applied Probability Society, as well as two National Science Foundation grants in 2007.

Gamarnik holds a BA in mathematics from New York University and a PhD in operations research from MIT.

Research interests

Probability, stochastic processes, queueing theory, random graphs and probabilistic analysis of combinatorial structures, algorithms and combinatorial optimization, statistics and learning theory.

Publications

• "Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average."
  Gamarnik, David, and Eren Kizildag. Annals of Applied Probability. Forthcoming. arXiv Preprint.

• "Sparse High-dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm."
  Gamarnik, David, and Ilias Zadik. Annals of Statistics. Forthcoming. arXiv Preprint.

• "The Overlap Gap Property and Approximate Message Passing Algorithms for p-spin Models."
  Gamarnik, David, and Aukosh Jagannath. Annals of Applied Probability Vol. 49, No. 1 (2021): 180-205. arXiv Preprint.

• "Low-Degree Hardness of Random Optimization Problems."
  David Gamarnik, Aukosh Jagannath, and Alexander S. Wein. In Proceedings of the 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, Durham, NC: November 2020. arXiv Preprint.

• "Explicit Construction of Rip Matrices is Ramsey-hard."
  Gamarnik, David. Communications on Pure and Applied Mathematics. Vol. 73, No. 9 (2020): 2043-2048. arXiv Preprint.

• "A Lower Bound on the Queueing Delay in Resource Constrained Load Balancing."
  Gamarnik, David, John N. Tsitsiklis, and Martin Zubeldia. Annals of Applied Probability Vol. 30, No. 2 (2020): 870-901.

• "Finding Cliques Using Few Probes."
  Feige, Uriel, David Gamarnik, Joe Neeman, Miklós Z. Rácz, and Prasad Tetali. Random Structures & Algorithms Vol. 56, No. 1 (2020): 142-153. arXiv Preprint.

• "Sparse High-dimensional Isotonic Regression."
  David Gamarnik, and Julia Gaudio. In Advances in Neural Information Processing Systems 32 (NIPS 2019), edited by Alina Beygelzimer, Emily Fox, Florence d'Alché-Buc, Hanna Wallach, Hugo Larochelle, and Roman Garnett. Vancouver, Canada: December 2019.

• "High-Dimensional Linear Regression and Phase Retrieval via PSLQ Integer Relation Algorithm."
  David Gamarnik, and Eren C. Kizildağ. In Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France: July 2019.

• "Uniqueness of Gibbs Measures for Continuous Hardcore Models."
  Gamarnik, David and Kavita Ramanan. The Annals of Probability Vol. 47, No. 4 (2019): 1949-1981.

• "Suboptimality of Local Algorithms for a Class of Max-cut Problems."
  Chen, Wei-Kuo, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman. The Annals of Probability Vol. 47, No. 3 (2019): 1587-1618.

• "Finding a Large Submatrix of a Gaussian Random Matrix."
  ​Gamarnik, David, and Quan Li. Annals of Statistics Vol. 46, No. 6A (2018): 2511-2561.