BIMSA >
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
组织者
马杰
, 本杰明·苏达科夫
演讲者
David Gamarnik
时间
2025年12月09日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899
(BIMSA)
摘要
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.