Description:

Title: Turing in the Shadows of Nobel and Abel: An Algorithmic Story Behind Two Recent Prizes, Part II

Abstract: The 2021 Nobel Prize in physics was awarded to Parisi “for the discovery of the interplay of disorder and fluctuations in physical systems.” The 2024 Abel Prize in mathematics was awarded to  Talagrand “for his groundbreaking contributions to probability theory and functional analysis, with outstanding applications in mathematical physics and statistics.” What remained largely absent in the popular descriptions of these prizes, however, is the profound contributions their works have had to the field of algorithms and computation. The methods developed by Parisi and Talagrand  have revolutionized the way we think algorithmically about optimization problems involving randomness, both classical and quantum.

In our talks we will explain how these ideas led to a remarkably precise characterization of which optimization problems admit fast algorithms, versus those which do not. The key obstruction to algorithms comes in the form of the Overlap Gap Property (OGP) which we will define and which originates in the works of Parisi and Talagrand. A range of examples we will consider include combinatorial optimization on random graphs, spin glasses, random perceptron and many others. 

In Part I of the lecture we will consider how OGP is an obstruction to ''static'' algorithms such as local algorithms, classical and quantum,  and Approximate Message Passing. In Part II we will discuss how OGP obstructs time dependent algorithms such as Glauber dynamics.