Overlap gap property: A topological barrier to optimizing over random structures
Many decision and optimization problems over random structures exhibit a gap between the existential and algorithmically achievable values, dubbed as statistics-to-computation gap. Examples include the problem of finding a largest independent set in a random graph, the problem of finding a near ground state in a spin glass model, the problem of finding a satisfying assignment in a random constraint satisfaction problem, and many more problems. At the same time, no formal computational hardness of these problems exists which would explain this persistent algorithmic gap.
In the talk we will describe a new approach for establishing an algorithmic intractability for these problems called the overlap gap property. Originating in statistical physics, and specifically in the theory of spin glasses, this is a simple to describe property which a) emerges in most models known to exhibit an apparent algorithmic hardness; b) is consistent with the hardness/tractability phase transition for many models analyzed to the day; and, importantly, c) allows to mathematically rigorously rule out a large class of algorithms as potential contenders, specifically the algorithms which exhibit noise insensitivity.
We will specifically show how to use this property to obtain stronger than the state of the art lower bounds on the depth of Boolean circuits for solving two of the aforementioned problems: the problem of finding a large independent set in a sparse random graph, and the problem of finding a near ground state of a p-spin model.
Joint work with Aukosh Jagannath and Alex Wein