We are sorry to announce that this lecture is cancelled. Please follow our website for updates.

Abstract

Many combinatorial optimization problems defined on random instances, such as random graphs, exhibit an apparent gap between the optimal values, which can be computed 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 barrier for designing fast algorithms bridging this gap is an intricate topology of nearly optimal solutions, in particular the presence of a certain Overlap Gap Property (OGP), which we will introduce in this talk. We will demonstrate how for many such problems the onset of the OGP phase transition indeed nearly coincides with algorithmically hard regimes and provides a provable barrier to a broad class of polynomial time algorithms. Our examples will include the problem of finding a largest independent set of a random graph, finding a largest cut in a random hypergrah, random NAE-K-SAT problem, the problem of finding a largest submatrix of a random matrix, the problem of finding a ground state of a p-spin model, and also many models in high-dimensional statistics and machine learning fields.