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.