Probability and Mathematical Physics Seminar

---

The algorithmic hardness threshold for continuous random energy models

Speaker: Pascal Maillard, CRM (Montréal) and Université Paris-Sud

Location: Warren Weaver Hall 512

Date: Friday, November 2, 2018, 11 a.m.

Synopsis:

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. I further discuss what insights this yields for understanding algorithmic hardness thresholds for random instances of combinatorial optimization problems.