Overlap gap property: a provable barrier to fast optimization in probabilistic combinatorial structures

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 hypergraph, the problem of finding a ground state of a p-spin model, and also many models in high-dimensional statistics and machine learning fields. The classes of algorithms ruled out by the OGP include local algorithms, Markov Chain Monte Carlo, Approximate Message Passing and low-degree polynomial based algorithms.

Joint work with Madhu Sudan, Wei-Cuo Chen, Dmitry Panchenko, Mustazee Rahman, Aukosh Jagannath and Alex Wein.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).