BIMSA >
Research seminar in Discrete Mathematics
Research seminar in Discrete Mathematics
Overlap Gap Property: A topological barrier to optimization in random structures
Overlap Gap Property: A topological barrier to optimization in random structures
Organizers
Jie Ma
, Benjamin Sudakov
Speaker
David Gamarnik
Time
Tuesday, December 9, 2025 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
Many optimization problem involving randomness exhibit a gap between optimal values on the one hand, and the best values achievable by known fast (polynomial time) algorithms. Two illustrative examples to be discussed in the talk are ground states of a spin glasses and largest submatrix of a random matrix. At the same time, the formal hardness of these problems in the form of the complexity-theoretic NP-hardness is lacking.
We introduce a new approach for understanding algorithmic intractability of such optimization problems, which is based on the topological disconnectivity of the space of near optimal solutions, called the Overlap Gap Property (OGP). The property traces back to the Parisi's replica symmetry breaking method, and the subsequent mathematically rigorous validation of it by Talagrand. We will prove that OGP is indeed a barrier to bridging such algorithmic gaps for large classes of algorithms, specifically stable (noise-insensitive) and online algorithms. It is notable that these are precisely the algorithms which achieve the best currently known values. Ground states of spin glasses and the largest submatrix problem will serve as illustration for these ideas.
We introduce a new approach for understanding algorithmic intractability of such optimization problems, which is based on the topological disconnectivity of the space of near optimal solutions, called the Overlap Gap Property (OGP). The property traces back to the Parisi's replica symmetry breaking method, and the subsequent mathematically rigorous validation of it by Talagrand. We will prove that OGP is indeed a barrier to bridging such algorithmic gaps for large classes of algorithms, specifically stable (noise-insensitive) and online algorithms. It is notable that these are precisely the algorithms which achieve the best currently known values. Ground states of spin glasses and the largest submatrix problem will serve as illustration for these ideas.
Speaker Intro
David Gamarnik is a Professor of Operations Research at the Operations Research and Statistics Group, Sloan School of Management of Massachusetts Institute of Technology. He received B.A. in mathematics from New York University in 1993 and Ph.D. in Operations Research from MIT in 1998. Since then he was a research staff member of IBM T.J. Watson Research Center, before joining MIT in 2005.
His research interests include discrete probability, optimization and algorithms, quantum computing, statistics and machine learning, stochastic processes and queueing theory. He is a fellow of the Institute for Mathematical Statistics, Institute for Operations Research and Management Science, and the American Mathematical Society. He is a recipient of the Erlang Prize and the Best Publication Award from the Applied Probability Society of INFORMS, and was a finalist in Franz Edelman Prize competition of INFORMS. He is a co-author of a textbook on queueing theory. He currently serves as an area editor for the Mathematics of Operations Research journal. In the past he served as an area editor of the Operations Research journal, and as an associate editor of the Mathematics of Operations Research, the Annals of Applied Probability, Queueing Systems and the Stochastic Systems journals.