Algorithms & Randomness Center (ARC)
David Gamarnik (MIT)
Monday, February 14, 2022
Klaus 1116 East - 11:00 am
Title: Overlap gap property: A topological barrier to optimizing over random structures
Abstract: Many decision and optimization problems over random structures exhibit a gap between the existential and algorithmically achievable values. 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 many more. 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 the input stability (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.
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836