The algorithmic hardness threshold for continuous random energy models

Jeudi 21 février 2019 14:00-15:00

Lieu : 3L15

Notes de dernières minutes : I will report on recent work with Louigi Addario-Berry on algorithmic hardness for finding low-energy states in the continuous random energy model of Bovier and Kurkova. This model can be regarded as a toy model for strongly correlated random energy landscapes such as the Sherrington—Kirkpatrick model. We exhibit a precise and explicit hardness threshold : finding states of energy above the threshold can be done in linear time, while below the threshold this takes exponential time for any algorithm with high probability. If time permits, I further discuss what insights this yields for understanding algorithmic hardness thresholds for random instances of combinatorial optimization problems.