Overlap Gap Property: a Provable Barrier to Fast Optimization in Probabilistic Combinatorial Structures

  • 11 November 2020
    4:30 PM
  • Mendel Museum´s Augustinian Abbey Refectory at Mendel Square

David Gamarnik is the Nanyang Technological University Professor of Operations Research at the MIT Sloan School of Management. His research interests involve probability, stochastic processes, queueing theory, random graphs and probabilistic analysis of combinatorial structures, algorithms and combinatorial optimization, statistics and learning theory. He served as a research staff member at the Department of Mathematical Sciences, IBM Research, where he worked on various projects with industrial applications, including disaster recovery, performance in business processes, call centers, and operational resilience. His research work has been recognized by awards of the 2004 Erlang Prize and the 2011 Best Publication Award from the INFORMS Applied Probability Society.

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.

Coffee Break at 4.00 PM

The lecture starts at 4.30 PM, however, you can arrive earlier at 4 PM to attend an informal coffee break, during which you can engage in a discussion with the speaker himself and get first-hand knowledge.

Where?

Mendel Museum's Augustinian Abbey Refectory at Mendel Square

Loading map…

Share event