The algorithmic hardness threshold for continuous random energy models

Jeudi 14 février 14:00-15:00 - Pascal Maillard - LMO

Résumé : 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.

The algorithmic hardness threshold for continuous random energy models  Version PDF