Many randomly generated constraint satisfaction problems 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 obstacle for designing algorithms bridging 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 how 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 of a graph, solving a symmetric version of a random K-SAT problem, the problem of finding a largest submatrix of a matrix with independent Gaussian entries, and high-dimensional sparse regression problem in statistics.
Joint work with Quan Li (MIT), Ilias Zadik (MIT) and Madhu Sudan (Harvard)