Speaker: David Gamarnik (MIT)

Title: From spin glasses to Boolean circuits lower bounds. Algorithmic barriers from the overlap gap property

Abstract: Many decision and optimization problems over random structures exhibit an apparent gap between the existentially optimal values 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. Unfortunately, at the same time no formal computational hardness results exist which  explains 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 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 a form of stability/noise insensitivity.

We will specifically show how to use this property to obtain stronger (stretched exponential) than the state of the art (quasi-polynomial) lower bounds on the size of constant depth Boolean circuits for solving the 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