Random Energy Models: Extremes, Complex temperature, Optimization – REMECO

This project aims at significantly advancing the understanding of the continuous random energy models (CREM), which are a class of toy models for strongly correlated random functions on a high-dimensional space such as mean-field spin glasses. We aim at investigating three different aspects: the distribution of its extreme values, the asymptotic behavior of the partition function at complex temperatures and the efficiency of optimization algorithms.

The CREM can be described as a Gaussian process on a tree whose covariance is a function A of the overlap. We want to obtain a precise description of the extreme values (and their structure) in the case where A is strictly concave which is missing up to this point. Another goal is to use these insights to study the behavior of the partition function of the CREM at complex temperature (for strictly concave A) and not only show that the phase diagram has seven phases as has been conjectured but also obtain a precise description of the limit. Last but not least we want to study the efficiency of optimization algorithms. For instance, we wish to investigate the behavior close to the algorithmic hardness threshold the existence of which has been obtained recently.