Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, December 4, 2018 - 3:00pm

Pascal Maillaird

CRM

Location

Temple University

Wachman Hall 617

Note the location change

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.