Visiting Speaker
David Gamarnik
Nanyang Technological University Professor of Operations Research at the Operations Research and Statistics Group, MIT
(Arguably) Hard On Average Optimization Problems in Random Graphs and High-Dimensional Statistics
Wed
Nov 1, 2017
Download TALK slides
2:00 pm
177 Huntington Ave
11th floor
ADD to calendar

Many combinatorial optimization problems on random instances exhibit an apparent gap between the optimal value, which can be estimated by non-constructive means, and the best values achievable by fast (polynomial time) algorithms. Through a combined effort of mathematicians, computer scientists and statistical physicists, it became apparent that a potential and in some cases a provable obstruction for designing algorithms that would bridge this gap is an intricate geometry of nearly optimal solutions, in particular the presence of a certain Overlap Gap Property (OGP). In this talk we demonstrate that for many such problems, the onset of the OGP phase transition indeed nearly coincides with algorithmically hard regimes. Our examples will include the problem of finding a largest independent set in a sparse random graph, finding a largest cut in a random hypergrah, the problem of finding a largest submatrix of a random matrix, and the high-dimensional sparse linear regression problem in statistics.

Joint work with Wei-Kuo Chen, Quan Li, Dmitry Panchenko, Mustazee Rahman, Madhu Sudan and Ilias Zadik.

about the speaker
David Gamarnik is a Nanyang Technological University Professor of Operations Research at the Operations Research and Statistics Group, Sloan School of Management of Massachusetts Institute of Technology. He received B.A. in mathematics from New York University in 1993 and Ph.D. in Operations Research from MIT in 1998. Since then he was a research staff member of IBM T.J. Watson Research Center, before joining MIT in 2005. His research interests include probability, theory of random graphs, optimization and algorithms, statistics and machine learning, stochastic processes and queueing theory. He is a recipient of the Erlang Prize and the Best Publication Award from the Applied Probability Society of INFORMS, and he was a finalist for Franz Edelman Prize competition of INFORMS. He is currently an area editor of Operations Research journal, associate editor of Mathematics of Operations Research, and he has been an associate editor of Annals of Applied Probability, Queueing Systems and Stochastic Systems journals in the past.

No upcoming events

Thank you! You have been added to our email list.

Oops! Something went wrong while submitting the form